HashTable实现

[TOC]

# Hash函数设计
## 整数
```
hash(126) = (1 * 10^2+2 * 101+6 * 10^0)
```
## 字符串
公式：
```
hash(code) = (c * B^3 + o * B^2 + d * B^1 + e * B^0) % M hash(code) = ((((c*B)+o)*B+d)*b+e) % M
hash(code) = ((((c%M)*B+o)%M*B+d)%M*B+e)%M
```
伪算法：
```
hash = 0;
i = 0;
for i < s.len
{
    hash = (hash*B + s[i])%M;
    i++;
}
```

## STL中hash function设计
```
template<typename Key> struct hash {};
inline size_t __stl_hash_string(const char* s)
{
	unsigned long h = 0;
	for (; *s; ++s)
		h = 5 * h + *s;
	return size_t(h);
}

struct hash<const char*>
{
	size_t operator()(const char* s)const { return __stl_hash_string(s); };
};

struct hash<char*>
{
	size_t operator()(char* s)const { return __stl_hash_string(s); };
};

struct hash<char>
{
	size_t operator()(char x)const { return x; };
};
更多的特别版本略.......
```

# HashTable的种类
## 平衡树
- 有M个地址
- 总共有N各元素
- 每个地址都是平衡树
- 时间复杂度O(log(N/M))

代码实现如下：

```
template<typename Key, typename Value>
class HashTable
{
public:
	HashTable(int M) :_M(M), _size(0)
	{
		_hashTable = new RBTree<Key, Value>[M];
		for (int i = 0; i < M; i++)
		{
			_hashTable[i] = RBTree<Key, Value>();
		}
	}

~HashTable()
	{
		delete[]_hashTable;
	}

public:
	int getSize() { return _size; }

void insert(const Key &k, const Value &v)
	{
		RBTree<Key, Value> rb = _hashTable[hash(k)];
		if (rb->containsKey(k))
		{
			rb->insert(k, v);
		}
		else
		{
			rb->insert(k, v);
			_size++;
		}
	}

Value remove(const Key &k)
	{
		Value ret;
		RBTree<Key, Value> rb = _hashTable[hash(k)];
		if (rb->containsKey(k))
		{
			ret = rb.remove(k);
			_size--;
		}
		return ret;
	}

void set(const Key &k, const Value &v)
	{
		RBTree<Key, Value> rb = _hashTable[hash(k)];
		if (rb->containsKey(k))
		{
			ret = rb->insert(k, v);
		}
		else
		{
			throw;
		}
	}
private:
	int hash(const Key &k)
	{
		return k;
	}
private:
	RBTree<Key, Value>* _hashTable;
	int _M;
	int _size;
};

```

## 链表法
- 有M个地址
- 总共有N各元素
- 每个地址都是链表
- 时间复杂度O(N/M)

结构如下所示：
![](https://leanote.com/api/file/getImage?fileId=5d2db76cab644166440075dd)

Simon 's Blog

导航

OHH,最近发表

这里随便填填,没事