Hash table - Revision history

Karl Jones at 01:05, 10 May 2016

2016-05-10T01:05:43Z

Karl Jones: /* External links */

2016-04-20T22:44:25Z

‎External links

Karl Jones: /* See also */

2016-02-22T15:37:25Z

‎See also

Karl Jones: Created page with "In computing, a '''hash table''' (or '''hash map''') is a data structure used to implement an associative array, a structure that can map keys to values. A hash ta..."

2016-02-20T14:34:31Z

Created page with "In computing, a '''hash table''' (or '''hash map''') is a data structure used to implement an associative array, a structure that can map keys to values. A hash ta..."

New page

In [[computing]], a '''hash table''' (or '''hash map''') is a [[data structure]] used to implement an [[associative array]], a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

== Description ==

Ideally, the hash function will assign each key to a unique bucket, but it is possible that two keys will generate an identical hash causing both keys to point to the same bucket. Instead, most hash table designs assume that hash collisions—different keys that are assigned by the hash function to the same bucket—will occur and must be accommodated in some way.

In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at (amortized[2]) constant average cost per operation.

In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets.

== See also ==

* [[Computing]]

== External links ==

* [https://en.wikipedia.org/wiki/Hash_table Hash table] @ Wikipedia

← Older revision		Revision as of 22:44, 20 April 2016
Line 18:		Line 18:

	* [https://en.wikipedia.org/wiki/Hash_table Hash table] @ Wikipedia		* [https://en.wikipedia.org/wiki/Hash_table Hash table] @ Wikipedia
		+
		+	[[Category:Computer science]]
		+	[[Category:Data structures]]

@@ Line 1: / Line 1: @@
-In [[computing]], a '''hash table''' (or '''hash map''') is a [[data structure]] used to implement an [[associative array]], a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
+In [[computing]], a '''hash table''' (or '''hash map''') is a [[data structure]] used to implement an [[associative array]], a structure that can map keys to values.
 == Description ==
 Ideally, the hash function will assign each key to a unique bucket, but it is possible that two keys will generate an identical hash causing both keys to point to the same bucket. Instead, most hash table designs assume that hash collisions—different keys that are assigned by the hash function to the same bucket—will occur and must be accommodated in some way.
-In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at (amortized[2]) constant average cost per operation.
+In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at (amortized) constant average cost per operation.
 In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets.

@@ Line 12: / Line 12: @@
 * [[Computing]]
 ==  External links ==
 * [https://en.wikipedia.org/wiki/Hash_table Hash table] @ Wikipedia