Hash算法

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数

Hash算法常见方法：

• 直接定址法：直接以关键字k或者k加上某个常数（k+c）作为哈希地址。
• 数字分析法：提取关键字中取值比较均匀的数字作为哈希地址。
• 除留余数法：用关键字k除以某个不大于哈希表长度m的数p，将所得余数作为哈希表地址。
• 分段叠加法：按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几* 部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。
• 平方取中法：如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照需求取中间的几位作为哈希地址。
• 伪随机数法：采用一个伪随机数当作哈希函数。
  Hash表的大小为素数的时候更加均匀

java中HashMap 和 HashTable

HashMap 与HashTable 的不同
1.HashTable 获取链表的下标是用%取模运算
2.HashMap默认的初始化大小为16，之后每次扩充为原来的2倍(扩充的大小是：数组的长度);
3.HashMap 去链表的下标是用&与运算
4.HashTable默认的初始大小为11，之后每次扩充为原来的2n+1。