Hash Table - Revision history

Savoundg at 16:49, 2 October 2020

2020-10-02T16:49:18Z

← Older revision		Revision as of 16:49, 2 October 2020
Line 1:		Line 1:
	An hash table is a key-value data structure.		An hash table is a key-value data structure whose main purpose is highly-efficient lookup.

	From the key, we derive a hash code and from a hash code an index that points to the value.		From the key, we derive a hash code and from a hash code an index that points to the value.

Savoundg at 15:06, 30 September 2020

2020-09-30T15:06:22Z

← Older revision		Revision as of 15:06, 30 September 2020
Line 3:		Line 3:
	From the key, we derive a hash code and from a hash code an index that points to the value.		From the key, we derive a hash code and from a hash code an index that points to the value.

	When two value has the same hash code or index, there is a collision. One of the solution to fix a collision is chaining. For the same hash code or index, a chain ~~(linked list)~~ of ~~value~~ is mapped.		When two value has the same hash code or index, there is a collision. One of the solution to fix a collision is chaining. For the same hash code or index, a chain of values is mapped.

			There is multiple ways to chain values:
			* linked list: the most common, the worst case lookup is O(n)
			* binary search tree: rarely used except for non-uniform distribution, the worst case lookup is O(log(n))
			* open addressing with linear probing: look for the next available spot in the table, sometimes at fixed offset; fast and space-efficient, but can cause ''clustering'' issue (when there is no available spot)
			* quadratic probing with double hashing
	The purpose of hash-table to provide a constant-time for insertion, find, or delete operations.		The purpose of hash-table to provide a constant-time for insertion, find, or delete operations.

Savoundg: Created page with "An hash table is a key-value data structure. From the key, we derive a hash code and from a hash code an index that points to the value. When two value has the same hash cod..."

2018-06-03T07:36:17Z

Created page with "An hash table is a key-value data structure. From the key, we derive a hash code and from a hash code an index that points to the value. When two value has the same hash cod..."

New page

An hash table is a key-value data structure.

From the key, we derive a hash code and from a hash code an index that points to the value.

When two value has the same hash code or index, there is a collision. One of the solution to fix a collision is chaining. For the same hash code or index, a chain (linked list) of value is mapped.

The purpose of hash-table to provide a constant-time for insertion, find, or delete operations.

== Resources ==
{| class="wikitable"
!
|-
|https://www.youtube.com/watch?v=shs0KM3wKv8
|}