哈希表定义
根据维基百科定义，散列表（Hash table，也叫哈希表），是根据关键字（Key value）而直接访问在内存存储位置的数据结构。也就是说，它通过把键值通过一个函数的计算，映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。 一个简单的例子就是，查字典时的过程，字典的索引（可能是笔画或者拼音）就是key，后面对应的页码就是根据哈希函数得出的你所查字的真实地址。
散列函数（哈希函数）
如果要实现哈希表，首先第一步是要确定关键字和存储位置的对应关系，即确定散列函数。一般来说，散列函数会满足下面几个条件：
- 对输入的值，总是可以得到一个固定长度的输出值
- 不同的输入值可能得到相同的输出值
构造散列函数有多种方式，比如直接寻址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法。
碰撞处理
由于对于不同的关键词，散列函数可能输出相同的值。即k1!=k2，但是f(k1)=f(k2)，这种现象称为碰撞（Collision）。所以，第二步还需要处理碰撞，常用方法有以下几种：
- 开放寻址法（open addressing）
- 单独链表法
- 双散列
- 再散列
python中的字典
在python中，字典就是一个哈希表实现。
typedef struct {
Py_ssize_t me_hash;
PyObject *me_key;
PyObject *me_value;
} PyDictEntry;
struct _dictobject {
PyObject_HEAD
Py_ssize_t ma_fill;
Py_ssize_t ma_used;
Py_ssize_t ma_mask;
PyDictEntry *ma_table;
PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
PyDictEntry ma_smalltable[PyDict_MINSIZE];
}
python的字典解决碰撞的方式是使用开放寻址法，在这就可以体现python的一个设计思路：利用空间换时间。
一道关于HashMap存储方式的面试题
偶然间在网上看到一道面试题，感觉很有意思：如果以自定义类型为key，放入HashMap后，我们在外部将key的属性进行更改，然后再用这个key从HashMap中可以取出什么元素？ 我觉得准确的答案应该是：这要看如何生成哈希值了。 在python的字典中，一般不会出现这个问题。因为对象的哈希值是固定，就是对象的id：
class T():
pass
print id(T())
139696630028048
当然我们还可以自定义哈希值：
class T():
def __init__(self, name):
self.name = name
def __hash__(self):
return hash(self.name)
这样，在用T的对象作为key时，其实就是使用的self.name的哈希值。在取值时，情况就稍微复杂些，字典不光会判断哈希值，还会判断对象是否相等。如果我们想通过修改属性来获取其他key的元素，我们可以重写__eq__()
class T():
def __init__(self, name):
self.name = name
def __hash__(self):
return hash(self.name)
def __eq__(self,r):
return self.name == r.name
dict = {}
t1 = T(name='t1')
dict[t1] = 1
t2 = T(name='t2')
dict[t2] = 2
t2.name = 't1'
print dict[t2]
1