链接：https://zhuanlan.zhihu.com/p/39785921
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
哈希链表
1.0 定义
根据设定的哈希函数（Hash（））以及处理冲突的方法将查找表的元素储存在一段有限的存储空间里的就得到哈希表
(a)哈希函数
(b)处理冲突
1.0.1数组和链表
数组和链表是组成数据结构的基础构建，他们各有优缺点例如:（1）数组容易查找但是数组不好实现增删的功能；（2）链表容易实现链表的增删除但是不容易查找
* 但是这两个数据结构得共性是都是按照（index）（某种顺序）来查找对应元素，但当我哦有成百上千个数据等待查找得时候，这种方法就显得很低效。
有没有一种方法，可以根据存储数据直接运算出一个地址，来存储数据。实现数据和地址的链接呢?（至少可以简化一大部分比较时间）（例如你要找KEY在字典里,你会直接到K目录下寻找KEY）
*得到了大致思路后需要做什么事情应该怎么构建哈希表
2.构造哈希函数得考虑要素以及方法
通过哈希函数hash（key）的运算要满足什么样的条件呢？
（a）对应性
数据（key）通过hash（）函数只得到一个对应index，并且通过index可以确定存放（key）相应数组序列；
（b）单向性
统一个引用内容通过hash（key）得到得index相同，但是计算出index相同但不代表同一个数据内容。
*好比：一个孩子（对象）通过可各种测试后得到的综合评级是优秀（index），那么就把这个孩子放到数组里优秀这一地址下，只要是这个孩子每一次通过测试，都是优秀，但并不代表优秀得就只有这个孩子；
（c）有冲突性
每一个对象运算出来得哈希code有可能出现相同的情况这时候就会有哈希冲突，在对象很多得时候这样是难免的。如何解决哈希冲突呢？
（二）解决冲突
（c.1.0）如果冲突寻找相邻或者新的存储空间(开放地址法)_
（c.1.1）离散性存放（线性增量再离散）（+-1，+-2）
（c.1,2）线性存放（）
在发生冲突得index+1或者-1来访问相邻存储空间是否空闲，若仍然冲突，就接着与第一次查询方式相同的继续递归检查下去，知道发现合适得寻访区域
(c.2.0）连地址法
（c.2.1）公共溢出区
*发生冲突得区域重新寻找一块公共溢出区域，存放数据，寻找数据的时候可以在公共区域里查找
但是。这些方法都直接或者间接意义上避开了公用hashcode，遇到，冲突选择回避冲突，寻找下一个合适地址，接下来这这个存储方式，就直接顺着冲突，中心建立一个存储方式，即将二维数组里存放的数据模型变化为链表，数据后面跟着指针，可以
*先按照hashcode查找数据
*在同一个hashcode下寻找数据
在很大程度上提高了工作效率
如图，哈希code0对应得是28，同时84发生冲突，那么就将84接应到28后，在查找84可先访问0，后遍历链表*那么什么样的hash函数是一个好得hash函数呢，他满足能够让对象比较均匀得分布在数组上。引出对hash函数得讨论。
（三）选取hash函数一般有以下几种方法
（a）直接定址法
根据数据自身得不重复特点，对应进行相加减，得到他的code例如：根据手机号码前3位和尾号来定义
（b）数字分析法
取数据得中间或者开头，或者选取，部分相加法则来创建相对特质得hashcode。
(c)用素数取模
（四）hash得应用
（1）站在java虚拟机得角度，在内存里有好多好多得对象，一个程序运行起来的时候，就会有很多很多得对象在内存里生成，程序寻找对象可能是一件效率不高得循环遍历得过程，往往采取hash编码来存取，对象，它独一无二得代表一个对象，通过这个编码就找到相应得对象。
但是，java虚拟机在实现hashcode得时候有一些问题，多个对象跟能对应同一个哈希编码，
在JAVA里object类里面有equal函数
x.equals(y)当x.y是同一个对象的时候应用返回true否则返回false。但是在String，Data里重写了equals方法，引用是同一类对象，并且内容一致（不一定要是相同对象）返回true或者否返回false
也可以重新定义equals方法来根据自己的需要来重写
*equal验证的实现
当你女朋友想让你买一支口红，你和她一起在商店里看到一款口红，但是钱没那够，然后你和你女朋友就回家准备拿钱买买，等你到店里的时候发现，口红被商家卖了，你女朋友就生气啊，吵着说要和今早上看的口红一摸一样，商家现在说他保证这支口红和早上内只一样。
public class Lipstick {
private int color;
private int wight;
private int high;
public Lipstick (int Color,int wight,int high) {
this.color=color;
this.wight=wight;
this.high=high;
}
public Lipstick () {}
}首先，重新拿三只口红，进行下面的操作
public class Textequal {
public static void main(String[] args) {
Lipstick a=new Lipstick();
Lipstick b=new Lipstick();
Lipstick c=new Lipstick();
System.out.println(a.equals(b));
}
}
结果是false原因很简单，因为就是三只口红，没啥参数，女朋友可不干
于是老板又拿出了相同参数的三是口红这回可行了吧看看结果
public class Textequal {
public static void main(String[] args) {
Lipstick a=new Lipstick(1,2,3);
Lipstick b=new Lipstick(1,2,3);
Lipstick c=new Lipstick(1,2,4);
System.out.println(a.equals(b));
System.out.println(a.equals(c));
}结果是都是false，第二个是false可以解释但是，第一个是为什么呢，这就是java虚拟机里两个对象就不一样的原因，得到的hashcode不一样，呐这样女朋友就没办法哄好了吗？
这里就可以重写equal方法你可以直接重写equal方法不管怎么样都返回true这样女朋友就开心的拿着个蜡烛回家，这就不太合适了
这里就考虑怎么实现equal方法
public class Lipstick {
private int color;
private int wight;
private int high;
public Lipstick (int Color,int wight,int high) {
this.color=color;
this.wight=wight;
this.high=high;
}
public Lipstick () {}
public boolean equals(Object obj) {
//不是空
if(obj==null)return false;
else {
//两个类型相等
if(obj instanceof Lipstick) {
///参数一样
Lipstick c=(Lipstick)obj;
if(this.color==c.color&&this.wight==c.wight&&this.high==c.high)
return true;
}
}
return false;
}
}这样就基本实现了equals的重写方法
（2）hashtabel的使用
(a)hashtable的创建
public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, Serializable
由此可见hashtabel继承了Dictionary并且继承了map接口
HashTable采用"拉链法"实现哈希表，它定义了几个重要的参数：table、count、threshold、loadFactor、modCount。
其中table：理解为存储链表的节点的数组；
count：指的是存储键的个数；不是hashtabel的存储容量
threshold：Hashtable的阈值，用于判断是否需要调整Hashtable的容量。threshold的值="容量*加载因子"。就是什么时候收割韭菜；
loadFactor：默认加载因子(.75)在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查找某个条目的时间（在大多数 Hashtable 操作中，包括 get 和 put 操作，都反映了这一点）。就是需不需要重新加载的因数
modCount：用来实现“fail-fast”机制的（也就是快速失败）。所谓快速失败就是在并发集合中，其进行迭代操作时，若有其他线程对其进行结构性的修改，这时迭代器会立马感知到，并且立即抛出ConcurrentModificationException异常，而不是等到迭代完成之后才告诉你（你已经出错了）
（b）构造方法
Hashtable<String, Integer> numbers
= new Hashtable<String, Integer>();
numbers.put("one", 1);
numbers.put("two", 2);
numbers.put("three", 3);要获取一个数字，可以使用以下代码：
Integer n = numbers.get("two");
if (n != null) {
System.out.println("two = " + n);
}
首先这是一个API对hashtabel的实践，找到一个number，和数值之间的关系
调用默认构造函数有五个方法，建议调用api查看原文档
（c）主要方法
put
public V put(K key,
V value)将指定 key 映射到此哈希表中的指定 value。键和值都不可以为 null。
通过使用与原来的键相同的键调用 get 方法，可以获取相应的值。
这里注意，最开始默认的
put方法的整个处理流程是：计算key的hash值，根据hash值获得key在table数组中的索引位置，然后迭代该key处的Entry链表（我们暂且理解为链表），若该链表中存在一个这个的key对象，那么就直接替换其value值即可，否则在将改key-value节点插入该index索引位置处。如下：
首先我们假设一个容量为5的table，存在8、10、13、16、17、21。他们在table中位置如下：
然后我们插入一个数：put(16,22)，key=16在table的索引位置为1，同时在1索引位置有两个数，程序对该“链表”进行迭代，发现存在一个key=16,这时要做的工作就是用newValue=22替换oldValue16，并将oldValue=16返回。
如果过了阀值就会有rehash（）
在put(33,33)，key=33所在的索引位置为3，并且在该链表中也没有存在某个key=33的节点，所以就将该节点插入该链表的第一个位置。
protected void rehash() {
int oldCapacity = table.length;
//元素
Entry<K,V>[] oldMap = table;
//新容量=旧容量 * 2 + 1
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
return;
newCapacity = MAX_ARRAY_SIZE;
}
//新建一个size = newCapacity 的HashTable
Entry<K,V>[] newMap = new Entry[];
modCount++;
//重新计算阀值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
//重新计算hashSeed
boolean rehash = initHashSeedAsNeeded(newCapacity);
table = newMap;
//将原来的元素拷贝到新的HashTable中
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
if (rehash) {
e.hash = hash(e.key);
}
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}最开始的时候的阀值初始值11、加载因子默认0.75，那么这个时候阀值threshold=8，当容器中的元素达到8时，HashTable进行一次扩容操作，容量 = 8 * 2 + 1 =17，而阀值threshold=17*0.75 = 13，当容器元素再一次达到阀值时，HashTable还会进行扩容操作，一次类推。很耗费时间
但是hashtable里的get方法就是根据key值来计算出相应的value，如果迭代出来没有或者没有这个值就返回null；
存在问题
1.hashmap和tabel的区别
2.hashtable的遍历
3，hashtabel的扩容
4.hashtabel的参数的基本应用
5.具体实现扩容机制，以及阀值得应用