Hashtable - Revision history

Suhridk: /* Collision Resolution */

2014-12-20T06:01:24Z

Collision Resolution

Suhridk at 05:43, 20 December 2014

2014-12-20T05:43:21Z

Suhridk: /* Hashing */

2014-12-18T03:24:48Z

Hashing

Suhridk at 08:55, 22 October 2012

2012-10-22T08:55:11Z

Suhridk at 08:36, 22 October 2012

2012-10-22T08:36:57Z

Suhridk: Created page with "* Hashing is designed to solve the problem of needing to efficiently find or store an item in a collection. It is a technique to narrow down the search space. * Hashing means usi..."

2012-10-22T08:34:54Z

Created page with "* Hashing is designed to solve the problem of needing to efficiently find or store an item in a collection. It is a technique to narrow down the search space. * Hashing means usi..."

New page

* Hashing is designed to solve the problem of needing to efficiently find or store an item in a collection. It is a technique to narrow down the search space.
* Hashing means using some function or algorithm to map object data to some representative integer value.
* One basic approach. Calculate a hash for each key and store the hash value in an array index of the same value. Store the key, value pair in the same index positions in other arrays.
* However, this approach suffers from wasted space in the array - for those array indexes for which corresponding hash values are never generated.

← Older revision		Revision as of 06:01, 20 December 2014
Line 22:		Line 22:
	* One solution to collision is called linear probing. i.e. Just place the item in the next available slot.		* One solution to collision is called linear probing. i.e. Just place the item in the next available slot.
	* Another solution is use buckets to store more than one item at each position.		* Another solution is use buckets to store more than one item at each position.
		+	* However the buckets can have large no. of items which makes searching through them also costly.
		+	* We need to redistribute evenly between the greater no. of buckets, leading to a decrease in the size of each individual bucket.
		+	* When to resize ? Monitor the load factor. No. of values/No. of buckets (No. of array indices). If it is too high, then some of the buckets are too large.
		+	* A good load factor is 0.75 - 75% full.

← Older revision		Revision as of 05:43, 20 December 2014
Line 15:		Line 15:
	* Distribute the keys over a larger range of values.		* Distribute the keys over a larger range of values.
	* Combining the above two, Ideally a hash function should distribute hash codes evenly over the range of integers.		* Combining the above two, Ideally a hash function should distribute hash codes evenly over the range of integers.
		+
		+	= Collision Resolution =
		+
		+	* Now when we calculate a hash for a key & find that there is a collision, we can resize the array & store all the keys separately.
		+	* However, this is expensive & there will be lots of wasted space in the array.
		+	* One solution to collision is called linear probing. i.e. Just place the item in the next available slot.
		+	* Another solution is use buckets to store more than one item at each position.

@@ Line 6: / Line 6: @@
 * However, this approach suffers from wasted space in the array - for those array indexes for which corresponding hash values are never generated.
 * Another problem is collisions - a single hash value can represent many keys.
 * To solve wasted space use : hashcode modulo arraysize.
 * To solve collisions use linkedlists to store key->value pairs for each hash value.
 = Hash function properties =

@@ Line 1: / Line 1: @@
 * Hashing is designed to solve the problem of needing to efficiently find or store an item in a collection. It is a technique to narrow down the search space.
 * Hashing means using some function or algorithm to map object data to some representative integer value.
@@ Line 6: / Line 8: @@
 * To solve wasted space use : hashcode modulo arraysize.
 * To solve collisions use linkedlists to store key->value pairs for each hash value.

← Older revision		Revision as of 08:36, 22 October 2012
Line 3:		Line 3:
	* One basic approach. Calculate a hash for each key and store the hash value in an array index of the same value. Store the key, value pair in the same index positions in other arrays.		* One basic approach. Calculate a hash for each key and store the hash value in an array index of the same value. Store the key, value pair in the same index positions in other arrays.
	* However, this approach suffers from wasted space in the array - for those array indexes for which corresponding hash values are never generated.		* However, this approach suffers from wasted space in the array - for those array indexes for which corresponding hash values are never generated.
		+	* Another problem is collisions - a single hash value can represent many keys.
		+	* To solve wasted space use : hashcode modulo arraysize.
		+	* To solve collisions use linkedlists to store key->value pairs for each hash value.