Hash散列[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。

为了速度而散列

HashMap速度总所周知是非常快的，但是为什么会这么快，是因为它的散列技术，下面简单理解一下散列知识

散列的价值在于速度，使得查询得以快速。一般容器查询的速度的瓶颈位于键的查询，采取的做法一般是对键进行排序，但散列则不是

散列的特点

散列的做法，通常把键保存到某个地方，存储一组元素最快的数据结构就是数组，所以用它来保存键的信息（不是键本身），但是由于数组是固定，不能调整大小，但是我们存储元素的数量有时候是不确定的。故而，有个难题，如果用数组保存不确定元素大小的值。

散列的做法，数组不保存键本身，而是通过键对象生成一个随机数字，用作数组的下标，这个数字就是我们通常见到的hashCode。解决了数组固定的问题，随之问题又来了，因为不同的键有可能会生成一样的下标，故而冲突。造成我们查询的时候，虽然在数组中找到相同的位置，但是却不是我们想要的值。我们查询是通过查询对象计算出一个散列码，如果能保证没有冲突，重复，那就可能有了一个完美的散列函数。

通常，冲突由外部链接处理，数组不直接保存值，而是保存值的list，然后遍历list，进行equals线性查询，这部分的查询自然会比较慢，但是如果散列函数好的话，每个位置都只有较少的值。因为，不是查询整个list，而是快速跳到数组的位置，只对很少的值进行比较，这既是hashMap快的原因了。

slot 和 bucket

散列中的槽位（solt）通常称为桶位，以内实际散列表的数组名称为bucket，
桶的数量都使用质数。为了能够自动解决冲突，使用了LinkedList，每一组新元素都自动添加到你list末尾的某个特定桶位中。关于泛型数组，你也可以创建数组的引用。向上转型这样也是很方便的，这样可以防止后面的代码中进行额外的转型。

pull

对于pull方法，针对键本身调用，生成hashCode，并且将其结果强制转换为正数。为了产生的数值适合bucket数组的大小，取摸操作符
将按照该数组的尺寸取模，如果该数组的某个位置是null，则创建一个新的LinkedList,一般过程是，查看该位置的list是否有相同的元素，有的话就把赋值给oldValue，然后用新的值取代旧的值，标记found用来跟踪是否找到旧的的值，如果没有，则将新的添加到list的末尾。

get 和 put

get()和put() 按照相同的方式计算在buckets数组的索引,得以保证计算的hashCode是相同的。如果此位置有LinkedList存在，进行查询

put(key,value)分析

先计算key的hash，然后区域作为bucket数组的下标，而bucket数组是一个LinkedList数组，如果发现没有，则new 一个List,如果存在，则遍历这个List，如果发现key值已经存在于这个List，则替换旧的值,oldValue = newValue,并设置found=true,如果key值不相同，则下一步为直接添加到List的尾部，这样也解决了hashcode相同的冲突