Code implementation of hash table based on linear detection

Theory of linear table detection method

Add elements to the hash table

Add elements and pay attention to two points ：

• Back traverse to find the free position is circular traverse , Otherwise, the access will be out of bounds
• When a hash conflict occurs to find a free location , There are two situations ： This position is always empty and the element is not missed ; This position is empty , The element that was released before was deleted .

Hash table query ：

Pay attention to writing code in linear detection ：

When we are looking for value When , First calculate the hash value and find that it should be placed in the subscript 3 The location of , Taking out the element at this position is not equal to value, Explain but put value A hash conflict occurred when the , visit 4 I found that the position was empty ,

• If this position is always empty , Never let go of elements . There is no need to look back at this time value 了 . Because if this position is always empty , At that time value If you want to put it, it must be here .
• If this position is empty , I've let go of elements before , But it was later deleted . At this point, you need to continue searching . Because, but value When , It is possible that the element of this position is still , therefore value I found a place to put it .

Hash table delete operation

We are deleting the elements in the bucket. They are not really deleted , Just changed the state of the barrel .

Hash table linear detection code implementation

#include<iostream>
using namespace std;

enum State
{
    
	STATE_UNUSE,// A bucket that has never been used 
	STATE_USING,// Barrels in use 
	STATE_DEL,// The bucket in which the element is deleted 
};
class Bucket
{
    
public:
	Bucket(int key=0,State state=STATE_UNUSE)
		:_key(key),_state(state){
    }
	int _key;// Store the data 
	State _state;// Storage status 
};
class HashTable
{
    
private:
	Bucket* _table;// Dynamic Hash table 
	int _tableSize;// The size of the barrel 
	int _useBucketNum;// Number of barrels in use 
	double _loadFactor;// Loading factor 
	// stay C++11 in the future , The integer type of static constant can be directly initialized in the class 
	static const int _primeSize = 10;// Prime size 
	static int _primes[_primeSize];// Prime table 
	int _primeIdx;// The prime subscript currently used 
	void expand()
	{
    
		++_primeIdx;
		if (_primeIdx == _primeSize)
		{
    
			throw "hashtable is too large,can not expand anymore";
		}
		Bucket* newTable = new Bucket[_primes[_primeIdx]];
		for (int i = 0; i < _tableSize; i++)
		{
    
			if (_table[i]._state == STATE_USING)
			{
    
				int idx = _table[i]._key % _primes[_primeIdx];
				int k = idx;
				do
				{
    
					if (newTable[k]._state == STATE_UNUSE)
					{
    
						newTable[k]._key = _table[i]._key;
						newTable[k]._state = STATE_USING;
						break;
					}
					k = (k + 1) % _primes[_primeIdx];
				} while (k != idx);
			}
		}
		delete[]_table;
		_table = newTable;
		_tableSize = _primes[_primeIdx];
	}
public:
	HashTable(int size = _primes[0], double loadFactor = 0.75)
		:_useBucketNum(0), _loadFactor(loadFactor), _primeIdx(0)
	{
    
		// Send the user's incoming size Adjust to the nearest relatively large prime number 
		if (size != _primes[0])
		{
    
			for (; _primeIdx < _primeSize; _primeIdx++)
			{
    
				if (_primes[_primeIdx] > size)
				{
    
					break;
				}
			}
			// User incoming size It's too big for the last number , Adjust to the last number 
			if(_primeIdx == _primeSize)
				_primeIdx--;
		}
		_tableSize = _primes[_primeIdx];
		_table = new Bucket[_tableSize];
	}
	~HashTable()
	{
    
		delete[]_table;
		_table = nullptr;
	}
	bool insert(int key)
	{
    
		// Consider expanding 
		double factor = _useBucketNum * 1.0 / _tableSize;
		if (factor > 0.75)
		{
    
			expand();
		}
		int idx = key % _tableSize;
		int i = idx;
		do
		{
    
			if (_table[i]._state == STATE_UNUSE)
			{
    
				_table[i]._key = key;
				_table[i]._state = STATE_USING;
				_useBucketNum++;
				return true;
			}
			i = (i + 1) % _tableSize;
		} while (i != idx);
	}
	bool erase(int key)
	{
    
		int idx = key % _tableSize;
		int i = idx;
		do
		{
    
			if (_table[i]._state == STATE_USING && _table[i]._key == key)
			{
    
				_table[i]._state = STATE_DEL;
				_useBucketNum--;
				break;
			}
			i = (i + 1) % _tableSize;
		} while (_table[i]._state != STATE_UNUSE && i != idx);
		return true;
	}
	bool find(int key)
	{
    
		int idx = key % _tableSize;
		int i = idx;
		do
		{
    
			if (_table[i]._key == key && _table[i]._state == STATE_USING)
			{
    
				return true;
			}
			i = (i + 1) % _tableSize;
		} while (_table[i]._state != STATE_UNUSE && i != idx);
		return false;
	}
};
int HashTable::_primes[_primeSize] = {
     3,7,23,47,97,251,443,911,1471,42773 };

int main()
{
    
	HashTable htable;
	htable.insert(12);
	htable.insert(24);
	htable.insert(38);
	htable.insert(15);
	htable.insert(14);
	cout << htable.find(12) << endl;
	htable.erase(12);
	cout << htable.find(12) << endl;
}