HashMap Data Structure: A Comprehensive Guide PDF

HASHING AND MAPS  DICTIONARY PROBLEM The dictionary problem is a classic computer science problem: the task of designing a data structure that maintains a set of data during 'search' 'delete' and 'insert' operations.  DICTIONARY PROBLEM...

HASHING AND MAPS  DICTIONARY PROBLEM The dictionary problem is a classic computer science problem: the task of designing a data structure that maintains a set of data during 'search' 'delete' and 'insert' operations.  DICTIONARY PROBLEM Portmanteau For example, we have a word we want to know the definition of. A portmanteau or portmanteau A dictionary can help us get word is a blend of words in which parts of multiple words are quickly from the word to the combined into a new word, as in smog, coined by blending smoke definition. and fog, or motel, from motor and hotel. In linguistics, a portmanteau is a single morph that is analyzed as representing two underlying morphemes.  DICTIONARY PROBLEM A standard solution to the dictionary problem is a hash table; in some cases, it is also possible to solve the problem using directly addressed arrays, binary search trees, or other more specialized structure ASSOCIATIVE ARRAY, MAP, SYMBOL TABLE, OR DICTIONARY an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears just once in the collection. All of them have Key Value Pairs A HashMap lets us go from a key to a value quickly! Value A portmanteau or portmanteau word is a blend of words in which parts of multiple words are combined into a new word, as in smog, coined by blending smoke and fog, or motel, from motor and hotel. In linguistics, a portmanteau is a single morph that is analyzed as representing two underlying morphemes. KEYS MUST BE UNIQUE To look something up, each key must be unique! VALUES CAN BE REPEATED It is OK to have two keys point to the same value RECALL: THE LOOKUP TABLE A lookup table is an array that replaces runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than undergoing an 'expensive' computation or input/output operation. Hashing is a slightly more complex form of a lookup table  Values HASHMAP Keys This structure allows Consider you to jump very accord quickly to the data minute related to a key evident Instead of having to look through evert item you can jump to the definition you want  A hash table (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 HASHTABLE or slots, from which the desired value can be found.  Ideally, the hash function will assign each key to a unique bucket, but most hash table designs employ an imperfect hash function, which might cause hash collisions where the hash function generates the same index HASHTABLE for more than one key. Such collisions 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 HASHTABLE arbitrary insertions and deletions of key- value pairs, at 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, HASHTABLE particularly for associative arrays, database indexing, caches, and sets.  Maps provide a way of using "associative arrays" that allow you to store data indexed by keys of any type you desire, instead of just integers as with arrays. Maps can be accessed using iterators that ADVANTAGES are essentially pointers to templated objects of base type pair, which has two members, first and second. First corresponds to the key, second to the value associated with the key. IMPLEMENTATION The most frequently used general purpose implementation of an associative array is with a hash table: an array of bindings, together with a hash function that maps each possible key into an array index. HASHING CAN BE USED TO BUILD, SEARCH, OR DELETE FROM A TABLE. Take a field in a record, known as the key Convert it through some fixed process to a numeric value known as the hash key This is the position to either store or find an item in the table. It’s numeric value will be in the range of 0 to n -1 where n is the maximum number of slots in the table. Hash function (math or programming) converts a key to a hash key Function used whenever we need access to the table  The input into a hash function is a key value The output from a hash function is an index of an array (hash table) where the object containing the key is located HASH FUNCTION EXAMPLE SIMPLIFIED HASH FUNCTION int hashCode(string key, int size) { int i, hash; for (hash = 0, i = 0; i < key.size(); i++) hash = (hash