Dictionary &
Implementation
What is a dictionary?
• Dictionary is a set which supports a limited set operations
• INSERT, DELETE, MAKENULL and MEMBER operations only
• Why do we require dictionary?
• An application where we do less insertions and deletions, but frequent look
up in an efficient way.
• There are many applications which requires the above given behaviors. Here
are some such examples
• Symbol tables in compilers: Compilers use dictionaries to store information about
variables, functions, and other symbols in the code.
• Routing tables in networking: Network devices use dictionaries to store routing
information, mapping network addresses to their corresponding routes.
• Session management: Web applications use dictionaries to store session information
for individual users, including login status, preferences, and shopping cart items.
Implementations
• Different data structures can be used for implementation of
dictionary data structure
• Almost all implementations of set ( e.g. sorted or unsorted linked list,
bit-vector, fixed length array with a pointer to the last entry in the array
)
• Most commonly used one is hashing ( constant time per operation)
• Open hashing ( external hashing)
• Closed hashing ( internal hashing)
Basic Idea behind open hashing
• Essential idea:
• Hash Function: A mathematical function that takes an input (key, a
dictionary member) and produces a hash code.
• Mapping to an Index: The hash code is used to determine the index in
the hash table where the key-value pair will be stored.
• Hash Table: A data structure that uses a hash function to map keys to
specific indices in an array.
Hash function an example
• Some preliminary from C++
• Casting : conversion of one type to another type
• Implicit – automatic conversion from larger to smaller , lower precision to higher
precision
• Explicit – performed by the programmer, examples:
• int x=45;
• double y = static_cast<double>(x); // Safe conversion to double
• int z = static_cast<int>(y); // Potential loss of precision
• string type in c++:
• string is a data type in c++ ( in C string a character array)
Hash function an example
• string type in C++ ( continuation)
• length() or size(): Returns the length of the string.
• empty(): Checks if the string is empty.
• clear(): Removes all characters from the string.
• append(str): Appends a string to the end.
• insert(pos, str): Inserts a string at a specified position.
• erase(pos, len): Erases a substring starting at a given position and of a
given length.
• find(str): Finds the first occurrence of a substring and returns its position.
• rfind(str): Finds the last occurrence of a substring and returns its position.
• substr(pos, len): Extracts a substring.
• compare(str): Compares two strings lexicographically.
• c_str(): Returns a C-style null-terminated character array representation of
the string.
Hash function an example
• First, what we want to store in our Remember what I said earlier:
dictionary? Hash Function: A mathematical function
• (say): names ( string type) that takes an input (key, a dictionary
member) and produces a hash code.
• Second, how big is our dictionary?
Mapping to an Index: The hash code is
• (say): B- entries used to determine the index in the hash
• Third: what is the range of index? table where the key-value pair will be
stored.
• Here: index is in the range [0, B-1]
Hash Table: A data structure that uses a
• What is then our hash function? hash function to map keys to specific
• A function which will map a name to an indices in an array.
integer in the range [0-B-1]
Hash function an example
I: 73, b: 98, o: 111, t: 116, m: 109, i=105
• Example illustration:
sum=0
• Input name : sum = 0+ static_cast<int>(“I”)=0+73=73
sum = 73+ static_cast<int>(“b”)=73+98=171
string name =“Ibotombi”; sum = 171+
• Mapping : static_cast<int>(“o”)=171+111=282
sum = 282+ static_cast<int>(“t”)=282+116=398
int sum=0;
sum = 398+
for (int i=0; i<[Link]();i++) static_cast<int>(“o”)=398+111=409
sum=sum+ static_cast<int>(name[i]); sum = 409+
return (sum % B) static_cast<int>(“m”)=409+109=518
sum = 518+ static_cast<int>(“b”)=518+98=616
sum = 616+ static_cast<int>(“i”)=616+105=721
Hash value = 721% (B=21)=7 in the range
[0-20]
Open Hashing
• Basic Idea:
• Essential dictionary members are partitioned into a finite
number of classes, commonly referred to as “buckets”.
• Dictionary members in each bucket is maintained in a
linked list.
• To search a particular bucket, an array of “headers” of
the linked list is maintained in an array, indexed by the
bucket no. from 0 to B-1.
• Choose a hash function, which maps a given “name” ( a
dictionay member” to a integer in the range from 0 to B-1.
• In a summary:
• The elements on the ith list are the members of the dictionary being
represented that belong to class i, that is, the elements x in the set such
that h(x) = i.
Source : Alfred V. Aho [Link] . Data Structures And Algorithms
Closed Hashing
• A closed hash table keeps the dictionary members in the bucket table itself, rather than using that
table to store list headers.
• Collision:
• We can put only one element in any bucket.
• If we try to place x in bucket h(x) and find it already holds an element, a collision occurs.
• Collision Resolution:
• Probing
• We try each of the alternative locations, in order, until we find an empty one. If none is empty, the table is full, and we cannot insert
x.
• Formally, a sequence of hash function hi(x) = (hash(x) + f(i)) mod TableSize, with f(0)=0 is tried in succession. The function “f”
is the collision resolution techniques.
• Linear Probing :
• f(i)=i, primary (block of contiguously occupied cells )clustering is the major problem. Primary clustering happens when
multiple keys hash to the same location
• Quadratic Probing :
• f(i) = i2, secondary clustering is a problem. Secondary clustering happens when keys hash to different
• locations, but the collision-resolution has resulted in new collisions.
• Double Hashing:
• f(i) = i*hash2(x), use a second hash function, hash2(x)=R – (x mod R) where R is a prime smaller than TableSize
Illustration : Linear Probing
S= {89,18,49,58,69} h(k) = k mode TableSise, TableSize=10
Cell Hash Table
Index Index = 89 mode 10 = 9
Index= 18 mode 10 = 8
0 49 Index = 49 mode 10 = 9 (collision), Linear probing will start
1 58 Index = (h(49)+1) mode 10 = 0, empty cell so insert 49 in cell 0
2 69 Index = 58 mode 10 = 8 (collision), Linear probing will start
Index = (h(58)+1) mode 10 = 9 (collision), probing continued
3 Index = (h(58) + 2) mode 10 = 0 (collision), probing continued
4 Index = (h(58) + 3) mode 10 = 1 empty cell so insert 58 in cell 1
5 Index = 69 mode 10 = 9 (collision), Linear probing will start
Index = (h(58)+1) mode 10 = 0 (collision), probing continued
6 Index = (h(58) + 2) mode 10 = 1 (collision), probing continued
7 Index = (h(58) + 3) mode 10 = 2 empty cell so insert 69 in cell 2
8 18
Average Prob required for finding a value?
9 89
Illustration : Quadratic Probing
S= {89,18,49,58,69} h(k) = k mode TableSise, TableSize=10
Cell Hash Table
Index Index = 89 mode 10 = 9
Index= 18 mode 10 = 8
0 49 Index = 49 mode 10 = 9 (collision), Linear probing will start
1 Index = 7- (49 mod 7 ) = 7 empty cell so insert 49 in cell 7
2 58 Index = 58 mode 10 = 8 (collision), Linear probing will start
Index = 7- (58 mod 7 ) = 5 probing continued
3 69 Index = (h(58) + 22) mode 10 = 2 empty cell so insert 58 in cell 2
4 Index = 69 mode 10 = 9 (collision), Linear probing will start
5 Index = (h(58)+12) mode 10 = 0 (collision), probing continued
Index = (h(58) + 22) mode 10 = 3 empty cell so insert 69 in cell 3
6 49
7
8 18
9 89
Illustration : Double Hashing Probing
S= {89,18,49,58,69} h(k) = k mode TableSise, TableSize=10
Cell Hash Table
Index Index = 89 mode 10 = 9
Index= 18 mode 10 = 8
0 69 Index = 49 mode 10 = 9 (collision), Linear probing will start
1 Index = 7 – (49 mod 7)= 7, insert 49 in cell 6 which is 7 cells away from
2 cell 9
Index = 58 mode 10 = 8 (collision), Linear probing will start
3 58 Index = 7- (58 mod 7) = 5, insert 58 in cell 3 which is 5 cells away from cell
4 8
5 Index = 69 mode 10 = 9 , insert 69 in cell 0 which is 1 cells away from cell
9
6 49 Insert 60
7
Which cells will be probed?
8 18
60 mod 10 = 0 collision
9 89 7- (60 mod 7)=3 celss away
2* (7-(60 mod 7 ) = 2*3 = 6 cells away
Illustration of Behaviors Probing Methods
Shaded squares are occupied and black ones indicate where the key is inserted
Handling Deletion • Trick is to use a deletion marker, special
value (in addition to empty) for cells whose
keys have been deleted, called, say
“deleted”.
• If the entry is marked deleted this means
that the slot is available for future
insertions.
• If the member function comes across
such an entry, it should keep searching.
The searching stops when it either finds the
key or arrives at a cell marked “empty” (key
not found).
Closed Hashing
template<int MAXSIZE> public:
class Dictionary{ Dictionary();
private:
void makeNull();
struct element{
string member; bool member( string & thisname) const;
bool empty; void insert (string & thisname);
bool deleted; void remove( sting & thisname)
};
struct element hashTable[MAXSIZE];
// helper functions };
int locate( string & thisname);
int locate_l( string & thisname);
int hash(const string & thisname);
Closed Hashing
Locate function
• locate scans DICTIONARY from the bucket for h(x) until either x is found, or an empty bucket is found,
or it has scanned completely around the table, thereby determining that the table does not contain x.
locate returns the index of the bucket at which it stops for any of these reasons
Steps:
initial := h(x); // initial prob location
i := 0; // prob offset possible range 0- MAXSIZE-1
while (i < MAXSIZE) // till all offsets are tried
&& (hashTable [(initial +i) mod MAXSIZE ].memeber <> x) // till x not found
&&(hashTable [(initial + i) mod MAXSIZE].empty <> true) // till an empty cell in not found
do
i := i + 1; // try the next offset
return ((initial + i) mod MAXSIZE)
Closed Hashing
Locate_l function
• like locate, but it will also stop at and return a deleted entry
Steps:
Left to you
Closed Hashing
MEMBER function
begin
if hashTable [locate(thisname)].memeber == x then return (true) else return (false)
end; { MEMBER }
}
Closed Hashing
INSERT function
int bucket;
begin
if hashTable[locate (x)].member = = thisname then return; // x is already in A
bucket := locate_1(thisname);
if (hashTable [bucket].empty ) or (hashTable[bucket]. deleted) then
hashTable [bucket].member = thisname
else
cerr<<“INSERT failed: table is full”
end // end of insert
}
Closed Hashing
Function DELETE
int bucket;
begin
bucket := locate(thisname);
if (hashTable [bucket].member = = thisname) then
hashTable [bucket].deleted = true;
end // end of DELETE
Efficiency of Open Hashing
• Average time per dictionary operation in an open hash table.
• B buckets and N elements are stored in the hash table, then on the
average every bucket has N/B members, and we expect that an
average INSERT, DELETE, or MEMBER operation will take O(1 +
N/B) time. The constant 1 represents the time to find the bucket, and
N/B is the time to search the bucket.
• If we can choose B to be about N, this time becomes a constant per
operation. Thus, the average time to insert, delete, or test an
element for membership, assuming the element is equally likely to
be hashed to any bucket, is a constant independent of N.
• We can construct a hash table with N elements in time O(N(1 + N/B)).
By choosing B equal to N this becomes O(N).