散列 是一种无需查找、只用元素的查找键确定元素索引的方法 。（数组本身就是一个散列） 。
散列函数 使用一个查找键，在散列表中产生一个元素的整数索引 。
完美的散列函数 将每个查找键映射为一个不同整数，以改整数作为散列表的索引正恰当 。
典型的散列函数 不是完美的，因为它们可以允许不只一个查找键映射到同一个索引，导致散列表的冲突 。
任何函数都可以作为散列函数，但是不一定是一个好的散列函数，好的散列函数必须，使冲突最少、计算快 。（为了减少冲突的几率，应该选择使元素均匀地分布在散列表中的散列函数）
计算散列码
类类型散列码
JAVA的积累Object有一个方法hashCode返回一个整数散列码 。如果每一个类不覆盖hashCode，该方法就返回由调用对象的内存地址导出的一个int值 。为了对词典之类的实现有用，散列必须将相等的对象映射到散列表中的相同位置 。因此应定义自己版本的hashCode ；
方法hashCode的准则：
如果一个类覆盖了方法equals，则应该覆盖hashCode
如果方法equals认为两个对象相等，则hashCode对这两个对象必须返回相同的值
如果在程序执行过程中一个对象不只一次调用hashCode，并且如果在这一段时间内对象的数据保持不变，则hashCode必须返回相同的散列码 。
在同一程序的两次执行过程中，对象的散列码可以不同 。
字符串的散列码
通常，首先为字符串的每一个字符分配一个整数，然后相加 。但是这样会造成很多冲突，同时散列表也是非常稀疏的 。
更好的办法使将每个字符的Unicode值乘以一个基于该字符在字符串中位置的因子，再相加 。
具体的说：
字符串s含有n个字符，并且u i u_iu
i
是s中第i个字符的Unicode值，则对某个正整数g，散列码可以有如下形式：u 0 g n − 1 + u 1 g n − 2 + . . . + u n − 2 g + u n − 1 u_0g^{n-1}+u_1g^{n-2}+...+u_{n-2}g^+u_{n-1}u
0
?
g
n−1
+u
1
?
g
n−2
+...+u
n−2
?
g
+
u
n−1
?
这个计算可能导致溢出，特别是对于长字符串更是如此 。但Java忽略这些溢出，并且对于适当选择g，其结果是合理的散列码 。Java类String中目前的方法hashCode使用这个公职并以31作为g值 。但是应意识到，移出可能导致负的结果 。不过可以在将散列码压缩为散列表的恰当索引时加以处理 。
基本类型的散列码
对于位数在int型一下的可以用查找键本身转换成int作为散列 。对于其他位数多余int的类型 ，可以利用它们内部二进制表示 。如果查找键是long类型的整数，一种是直接转换成int，但是会忽略掉高32为带来的影响 。另一种是将它分为若干部分，然后再使用假发或者抑或这样的按位布尔运算将这些部分结合起来，这个过程称为折叠 。
将散列码压缩为散列表的索引
缩放一个整数使之位于一个给定取值范围内通常使用取模运算 。取模后的奇偶性，c % n c % nc%n 如果n为偶数那么结果的奇偶性于c的奇偶性相同 。（注意：基于呢村子之的散列码通常是偶数）散列表的索引就会有相同的偏向 。因此n只能是奇数，索引才能使均匀的 。
散列表的长度应该是素数n，则如果使用c % n c%nc%n将正的散列码c压缩为索引，索引将在0到n-1之间均匀粉不 。
如果c是负数，那么结果僵尸1-n到0之间，结果为0没关系，但如果结果为负，令它加上n，就可以使之在1到n-1之间 。
冲突处理
线性探测开放定址
通过从初始散列索引开始考察散列中连续位置，并寻找下一个可用位置，以解决散列过程中的冲突 。
线性探测可以检测散列表中每一个位置 。因此只要散列表不是满的，这种探测就可以确保add操作的成功 。
删除 从一个位置删除元素的最简单的方式是将null放进这个为置 。虽然散列表中在探测到从未使用过的位置应该终止查找，但是已用过且现在可重新使用的位置不应该终止查找 。
因此需要区分散列中三种位置：
被占用—该位置引用了词典中一个元素
空闲—该位置含有null并历来如此
可用—该位置的元素从词典中删除
开放定址处理冲突时词典操作所需的查找
为了检测一个位置，getValu(key)在探测序列中查找key 。它检测现有的元素，忽略处于可用状态的位置，查找终止于key被周到时或遇到null时 。
推荐阅读
- 详解Java使用Jsch与sftp服务器实现ssh免密登录
- Nginx 实现 Rewrite 跳转
- javascrip基础：var，let和const区别在哪里
- oracle实现按天，周，月，季度，年查询排序方法
- JavaScript Dom 绑定事件操作实例详解
- 一文帮你读懂Java浮点数的存储原理
- Java主流数据库连接池优劣及未来
- 超好用的 Java 开源 验证码 神器
- 英飞凌毫米波雷达芯片，实现可穿戴血压传感
- 卫星|我国成功发射高分三号03星：实现1米分辨率、1天重访