Shulou(Shulou.com)06/02 Report--

This article is about what the linear detection algorithm of hash table in java data structure is. The editor thinks it is very practical, so I share it with you. I hope you can get something after reading this article. Let's take a look at it with the editor.

The common methods to construct a hash table are:

Division residue method-the remainder obtained by dividing the key value by a number no more than the hash table length m is the hash address. HashKey= Key% P.

Direct addressing method-take a linear function of a keyword as the hash address HashKey= Key or HashKey= A*Key + BA, B as a constant.

Here I mainly use the method of division residue Hash (key) = Key%P, (P here is the length of the hash table) p it is better for primes to consider reducing the cause of the hash conflict. I am not too concerned about the hash table length 10 here, see the linear detection graph.

One of the problems often encountered in hash tables is hash conflicts.

What is a hash conflict? Hash conflict means that different keywords are mapped to the same hash address by the same hash function.

There are two main methods to solve the hash conflict: linear detection and secondary detection.

Here, I will describe the principle of linear detection in the following figure:

Linear detection

The linear probe code is as follows:

# define _ CRT_SECURE_NO_WARNINGS 1#includeusing namespace std;#include// linear probe specialization processing can handle custom type data enum State {EMPTY,// the location unstored element DELETE,// the location element has been deleted EXIST,// the location element}; / deal with the basic type templatestruct DefaultFuncer {size_t operator () (const K & key) {return key;}} / / handle the custom type templatestruct DefaultFuncer {size_t value = 0; size_t operator () (const string& str) {for (int I = 0; I < str.size (); iTunes +) {value + = str [I];} return value;}} Templateclass HashTable {public: HashTable (): _ size (0), _ capacity (0), _ state (NULL), _ table (NULL) {} HashTable (size_t size): _ size (0), _ capacity (size), _ state (new State [size]) _ table (new K [size]) {for (int I = 0) I < _ capacity; iTunes +) / / all states are initialized to EMPTY {_ state [I] = EMPTY;}} / / Linear probe calculates the location where elements are stored (assuming no hash conflict) int _ HashFunc (const K & key) {HashFuncer hf; return hf (key)% _ capacity / / Anonymous object calls operator () / * return HashFuncer () (key)% _ capacity;*/} void Swap (HashTable tmp) {swap (_ size, tmp._size); swap (_ capacity, tmp._capacity); swap (_ state, tmp._state); swap (_ table, tmp._table) } void _ CheckCapacity () {HashTable tmp (2*_capacity); for (int I = 0; I < _ capacity; iTunes +) {tmp.Insert (_ table [I]);} Swap (tmp) } bool Insert (const K & key) {/ / static hash table / * if (_ size = = _ capacity) {cout

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.