1.哈希表概念2.冲突概念3.冲突避免4.哈希函数的设计
4.1哈希函数的设计要求4.2key为整型哈希函数设计4.3其它数据类型如何设计哈希函数4.4现成的哈希函数 5.哈希冲突的解决思路
5.1闭散列(线性探测法)5.2开散列5.3冲突严重时的解决办法 6.负载因子7.基于拉链法哈希表的代码实现
1.哈希表概念1.顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时必须要经过关键码的多次比较，顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log2N),搜索的效率取决于搜索过程中元素的比较次数。
2.理想的搜索方法可以不经过任何比较，一次直接从表中得到想要搜索的元素。如果构造一种存储结构，通过某种函数，使元素的存储位置与它的关键码·之间能够建立一一映射的关系，在查找时也可以很快找到该元素。
3.哈希表典型的以空间换时间的解决思路，利用数组的随机访问特性来最大化查找效率，可以牺牲一部分空间，换来时间的高效。
例如：判断一组数中{8,5,9,6,7,3,5}3这个元素是否存在?
此时最大值为9，则开辟一个长度为10的布尔型数组，将原数组的元素和数组的下标建立联系。数组下标=元素的值，布尔数组中若元素出现则对应下标置为true.
boolean[] ret=new boolean[10]; ret[3]=true;
当我需要查找元素3时是否在集合中，只需要取出ret[3]看这个值是否为true即可，时间复杂度为O(1).
4.哈希函数：将特定的“键”通过一定的函数运算得到一个整数(作为数组的索引)
5.哈希方法中使用的转化函数称为哈希函数，构造出来的表叫做哈希表。
数据集合{1,7,6,4,5,9};
不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
3.冲突避免由于哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，所以冲突的发生是必然的，但我们能做的应该是尽量降低冲突率。
4.哈希函数的设计 4.1哈希函数的设计要求1.一致性：
key1=key2时，则hash(key1)=hash(key2)，且无论进行多少次哈希函数运算，key不变，hash值是不变的。
2.高效性：
哈希函数的运算不能太耗时，尽量可以立即计算得出，小数据范围的取模运算就是一个高效的。
3.均匀性：
不同的key，经过hash运算后尽量避免“冲突”，这里的哈希冲突就是指key1 != key2时，hash(key1)=hash(key2),举个例子，现在数组长度为10，我们hash()计算后的值就只分布在[0…2]这个区间上，此时就是一个不均匀的分布。
1.简单的做法就是“取模”，数值不大时可以直接取模，一般来说取模用素数。
2.为何最简单的做法要取模？
取模可以把不同跨度的数据映射成一个小数据范围内的数字。
3.负整数怎么办？
将负整数的值求abs(绝对值)后进行哈希运算。
x & 0x7fffffff//这实际就是把x转换为正整数4.3其它数据类型如何设计哈希函数
1.总的思路就是转为整型。
2.浮点数(计算机中就是用整数模拟小数的)和字符(存储的时候也按照编码规则转为整型存储)。
3.字符串->整型(按照进制转换)
此时可以得到一个通用公式：任意字符串=C B^x*
B：用户选的进制数
x就是当前字符C的位数
4.其它数据类型->String- >整型
1.一般而言，不需要自己设计哈希函数，直接用现成的即可。
2.md3,md4,md5.以MD5为例，MD5主要是给String计算哈希值。
MD5的三大特点：
(1)定长：无论输入的数据有多长，得到的MD5值长度固定(16或32位)。
(2)分散:如果输入的数据稍有变化，得到的MD5值相差很大。
(3)不可逆：根据任意值计算出一个MD5值很容易，但是想根据得到的MD5还原为原数据基本不可能。
MD5的应用非常广泛：
1.作为hsah值(不能直接作为索引，一般在得到MD5之后进行再次取模得到数组索引)。
2.用于加密：MD5的不可逆。
3.对比文件内容：一般在下载大文件时，一个MD5值，用来判断是否损坏，源文件10G的文件固定MD5值，下载后的文件，MD5值和源文件不同(下载过程中文件有损坏，部分丢失)。
哈希冲突就是指“不同的key经过哈希函数后得到了相同的值”，无法避免。哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。哈希冲突有两种常用思路：
5.1闭散列(线性探测法)1.闭散列：也叫开放定址法或者线性探测法，当发生哈希冲突时，找冲突位置的旁边有没有空闲位置(好插入难查找，更难删)。
2.例如向往哈希表中添加44这个元素，先通过哈希函数计算哈希地址，下标为4，因此44理论应该插在该位置，但是该位置已经放了值为4的元素，即发生了哈希冲突。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
(1)插入：
通过哈希函数获取待插入元素在哈希表中的位置。
如果 该位置没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。
(2)删除：采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索，比如删除元素4，如果直接删除掉，44查找起来可能会受影响，因此线性探测采用 标记的伪删除法来删除一个元素。
1.开散列法又叫做链地址法，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头节点存储在哈希表中。
我们可以发现开散列的每个桶中放的都是发生哈希冲突的元素。
开散列，可以看做是把一个大集合中的搜索问题转化为在小集合中做搜索了。
哈希桶可以看做将大集合的搜索问题转换为小集合的搜索问题了，那如果冲突严重，
例如：
1.每个桶的背后是另一个哈希表。
2.每个桶背后是一颗搜索树。
1.负载因子：描述一个哈希表的拥挤程度。
负载因子=元素个数/数组长度
2.java的系统库限制了负载因子为0.75
3根据负载因子来动态判断哈希表的扩容。
当元素个数>=数组长度 *负载因子，此时认为哈希表中冲突比较多，可以考虑扩容(数组长度变为原来的一倍)
负载因子越大，冲突机率越大，效率越低
负载因子越小，冲突几率小，但浪费空间
3.阿里要求负载因子保持在10左右，容许每个数组后链表的平均长度为10，找到时间和空间的平衡点。
HashMapBylink.java:
package hash;
public class HashMapBylink {
// 实际存储的每个节点,冲突时使用单链表链接冲突节点
private class Node {
int key;
int val;
Node next;
public Node(int key, int val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
// 实际存储的元素个数
private int size;
// 取模数,默认使用数组长度
private int M;
// 默认哈希表的长度
private static final int DEFAULT_CAPACITY = 16;
// 默认的负载因子
private static final double LOAD_FACTOR = 0.75;
// 实际存储Node节点的数组
private Node[] table;
public HashMapBylink() {
this(DEFAULT_CAPACITY);
}
public HashMapBylink(int initCap) {
this.table = new Node[initCap];
this.M = initCap;
}
public int put(int key,int value) {
// 1.先求key的hash值
int index = hash(key);
// 2.判断当前哈希表中是否已经存在了这个key，若存在，更新为value，返回旧的value
// table[index] 就是链表的头节点
for (Node x = table[index];x != null;x = x.next) {
if (x.key == key) {
// 此时哈希表中已经包含了key，更新为新的value，返回旧的value
int oldVal = x.val;
x.val = value;
return oldVal;
}
}
// 3.此时key不存在，新建一个节点头插入相应的链表中(原链表头节点 - table[index])
Node newNode = new Node(key,value);
Node head = table[index];
newNode.next = head;
// 更新原先头节点的指向为当前节点
head = newNode;
table[index] = head;
size ++;
// 4.扩容 TODO
if(size >= LOAD_FACTOR * table.length) {
resize();
}
return value;
}
private void resize() {
Node[] newTable = new Node[table.length << 1];
this.M = newTable.length;
// 遍历原哈希表
for (int i = 0; i < table.length; i++) {
// 取出每个链表的结点，然后映射到新哈希表中
// 循环进行的条件，此处不能直接使用cur = cur.next
Node next = null;
for (Node cur = table[i];cur != null;cur = next) {
next = cur.next;
int newIndex = hash(cur.key);
// 头插入新哈希表中
cur.next = newTable[newIndex];
newTable[newIndex] = cur;
}
}
this.table = newTable;
}
public boolean remove(int key,int value) {
int index = hash(key);
// 链表的删除，判断头节点的情况
if (table[index].key == key) {
if (table[index].val == value) {
// 此时头节点就是待删除的节点
// head = head.next;
Node head = table[index];
table[index] = head.next;
head.next = null;
size --;
return true;
}
}
// 头节点不是待删除的节点
Node prev = table[index];
while (prev.next != null) {
if (prev.next.key == key) {
if (prev.next.val == value) {
// prev就是待删除节点的前驱
prev.next = prev.next.next;
size --;
return true;
}
}
prev = prev.next;
}
// 此时就不存在这个键值对
return false;
}
// TODO
public boolean containsKey(int key) {
return false;
}
// TODO
public boolean containsValue(int value) {
return false;
}
public int get(int key) {
// 求出当前key对应的索引
int index = hash(key);
// 遍历index对应的链表，返回key对应的value
for (Node x = table[index];x != null;x = x.next) {
if (x.key == key) {
return x.val;
}
}
// 此时key不存在
return -1;
}
// 最简单的对key取模
private int hash(int key) {
// 求绝对值
return (key & 0x7fffffff) % this.M;
}
}
运行结果：
