Chapter5 Hasing
Hasing， intertions， deletions， and finds in constant average time.
findMin, findMax and print in sorted order are not supported.
* See several methods of implementing the hash table.
* Compare these methods analytically.
* Show numerous applications of hashing.
* Compare hash table with binary search trees.
5.2 Hashing Function
Normal Implementation of hash
int hash(const std::string & key, int tableSize)
{int hashVal = 0;for(char ch : key)hashVal += ch;return hashVal % tableSize;
}
When table size is large ,the function does not distribute the keys well.
Normal tableSize is prime number.
/*** examine only first three letters*/
int hash2(const std::string & key, int tableSize)
{return (key[0] + 27 * key[1] + 729 * key[2]) % tableSize;
}
By Horner's rule. hk = k0 + 37k1 + 37^2k2.
/*** A hash routine for string objects.*/
unsigned int hash3(const std::string & key, int tableSize)
{unsigned int hashVal = 0;for(char ch : key)hashVal = 37 * hashVal + ch;
}5.3 Separate Chaining
A template implementation
/*** generic hash function object.*/
template <typename HashedObj>
class hash
{size_t operator()(const HashedObj &key){return 0;}
};/*** hash function object for string.*/
template <>
class hash<std::string>
{public:size_t operator() (const std::string & key){size_t hashVal = 0;for(char ch : key)hashVal = 37 * hashVal + ch;return hashVal;}
};/*** example for hash template object* this is a member function of a class* theLists is the size of the hash table.*/
template <typename HashedObj>
size_t myhash(const HAshedObj &x) const
{static hash<HashedObj> hf;return hf(x) % theLists.size();
}A example of a class that can be used as a HashedObj
// Example of an Employee class
class Employee
{public:const std::string &getName() const{return name;}bool operator==(const Employee &rhs) const{return getName() == rhs.getName();}bool operator!=(const Employee &rhs) const{return !(*this == rhs);}private:std::string name;double salary;int seniority;// additional private members not shown.
};template <>
class hash<Employee>
{public:size_t operator()(const Employee &item){static hash<std::string> hf;return hf(item.getName());}
};An implementation of HashTable template class
template <typename HashedObj>
class HashTable
{public:// the Big five.explicit HashTable(int size = 101): theLists(101){}~HashTable() = default;HashTable(const HashTable &rhs) = default;HashTable(HashTable &&rhs) = default;HashTable &operator=(const HashTable &rhs) = default;HashTable &operator=(HashTable &&rhs) = default;void makeEmpty(){for (auto &thisList : theLists)thisList.clear();}bool contains(const HashedObj &x) const{auto &whichList = theLists[myhash(x)];return std::find(begin(whichList), end(whichList), x) != end(whichList);}bool remove(const HashedObj &x){auto &whichList = theLists[myhash(x)];auto itr = find(begin(whichList), end(whichList), x);if (itr == end(whichList)) // not foundreturn false;whichList.erase(itr);--currentSize;return true;}bool insert(const HashedObj &x){auto &whichList = theLists[myhash(x)];if (find(begin(whichList), end(whichList), x) != end(whichList))return false; // already existed.whichList.push_back(x); // insert the element.// Rehash; ref section 5.5if (++currentSize > theLists.size())rehash();return true;}bool insert(HashedObj &&x);private:std::vector<std::list<HashedObj>> theLists;int currentSize;/*** example for hash template object* this is a member function of a class* theLists is the size of the hash table.*/size_t myhash(const HashedObj &x) const{static hash<HashedObj> hf;return hf(x) % theLists.size();}void rehash(){}
};load factor λ， the ratio of the number of elements in the hash table to the table size. Normal λ = 1.0 to guarantee the search time is O(1).
5.4 Hash Tables without Linked Lists
Due to the disadvantage of using linked list ，
there is a probing hash tables.
5.4.1 Linear Probing
The load factor λ = 0.5 for a hash table that doesn't use separate chaining.
Primary Clustering, means that any key taht hashes into the cluster will require several attempts to resolve the collision.
Expected number of probes using linear probing is (1 + 1/(1-λ)^2)/2 for insertions and unsuccessful searches
(1 + 1/(1-λ))/2 for successful searches.
Expected probe to skip is 1/(1-λ)
so the λ shoule be less than 0.5 is a reasonable value for linear probe.
5.4.2 Quadratic Probing
Standard deletion can not be performed in a probing hash table, because the cell might have caused a collision to go past it. require lazy deletion,
A inplementation of hash table using probing strategies.
/*
* Author: sesiria 2018
* hashtable implementation by probing strat