Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets and Dictionaries, Hashing - Coggle Diagram
Sets and Dictionaries
Sets
A set can be described as
an unordered collection (possibly empty) of distinct items called elements of the set.
Dictionaries
A set of elements with the options of searching, insertion and deletion.
- Elements are indexed by comparable keys
- Implementations: array, linked list,
hash tables, and balanced trees
Operations:
- void clear(Dictionary d);
- void insert(Dictionary d, Key k, E e); // reflect on: multiple entries
- E remove(Dictionary d, Key k); // reflect on: multiple entries
- E removeAny(Dictionary d); // alternative: getKeys
- E find(Dictionary d, Key k); // reflect on: multiple entries
- int size(Dictionary d);
Hashing
Space and time trade-off
- Worse space efficiency to get a better time efficiency
SLIDE: https://drive.google.com/file/d/1rbm8iEWPIZ6VB_eJowvuRu6mu9BQD9UQ/view
VIDEO: https://drive.google.com/file/d/1KU_EsBuLeoghXRUhYnej4RDMgVU15rGn/viewHashing: distributing keys among a one-dimensional array dictionaries
- Very efficient way to implement dictionaries
- Hash table: H[0..m − 1]
- Hash function: h : Key → 0..m − 1
h needs to satisfy somewhat conflicting requirements:
- Adequate relation between m and |Key|
- Distribute keys as evenly as possible
- Has to be easy to compute
Limitations:
- Not ideal in the presence of multiple entries per key
- Not ideal for accessing elements based on some order
- Not ideal for searching based on a range of keys
Collisions
- If m <| Key |, they will occur
- If m ≥| Key |, they still might occur
Collision resolution mechanisms:
- Open hashing (separate chaining)
- Closed hashing (open addressing)
Perfect hashing:
- No collisions at all
- Key is known and available beforehand
- Example: data access on a read-only CD
A better approach: sfold:
Algorithm: int h(string K)
- intLength ← length(K)/4;
- sum ← 0;
- for i ← 0 to intLength − 1 do
- ----sub ← substring(K, i ∗ 4, (i ∗ 4) + 4); // initial and final positions
- ----mult ← 1;
- ----for j ← 0 to 3 do
- --------sum ← sum + sub[j] ∗ mult;
- --------mult ← mult ∗ 256;
- sub ← substring(K, intLength ∗ 4); // initial position to the end
- mult ← 1;
- s ← length(sub);
- for j ← 0 to s − 1 do
- ----sum ← sum + sub[j] ∗ mult;
- ----mult ← mult ∗ 256;
- return abs(sum)%m; // abs = overflow and %
A first attempt: fold
Algorithm: int h(string K)
- s ← length(K);
- sum ← 0;
- for i ← 0 to s − 1 do
- ----sum ← sum + K[i];
- return abs(sum)%m; // abs = overflow and %
-
-