散列表（数据结构学习笔记）

散列

　　散列表的一般实现叫散列。是一种以常数平均时间执行插入、删除、查找的技术。理想的散列表结构是一个包含关键字具有固定大小的数组。典型情况是，一个关键字就是一个带有相关值的字符串。把表大小记MaxSize,通常使表在0-MaxSize之间变化。每个关键字都被映射到0-MaxSize之间的某个单元中。这个映射关系就是散列函数。理想情况函数保证任何关键字都映射到不同单元里，实践是不可能的。因数组有限大小，而关键字可无限多。因此要找德散列函数尽可能的使关键字均匀的分布在单元中。如图 git在0号单元，hub在2号单元里。散列基本思想清楚后，就是找一个合适的散列函数，确定两个关键字散列到同一个单元中时，要怎么处理，以及确定散列表的大小。

散列函数

　　一般来讲如果关键字是整数，可以简单的采用“KEY MOD SIZE”方式取得结果。一般size要使用素数。因为整数容易大量MODE 为0的情况出现。

　　几种散列函数的方式　　

        1.字符串的一种典型处理是转换ASCⅡ码之后相加

　　　2.由key 和27的方次做加法。 key[0]+key[1]*27+key[2]*27²

　　   3.程序根据Horner法则计算一个32的多项式。∑₀^size key(size-i-1)*32ⁱ    简单就是 (value << 5) - value + c;

散列冲突

　　一个元素在插入单元处已经被另外的一个元素占用，就会发生散列冲突。解决冲突的两种简单方法是

        1.分离链接法：

        2.开放定址法

 一致性散列

  http://www.codeproject.com/Articles/56138/Consistent-hashing

http://blog.csdn.net/cywosp/article/details/23397179/

散列表（数据结构学习笔记）

原文：http://www.cnblogs.com/RunStone/p/5654769.html