透过Java中的HashMap了解Map接口

一直以来似乎都有一个错觉，认为map跟其他的集合类一样继承自Collection，其实不然，Map和Collection在结构层次上是没有任何关系的，通过查看源码可以发现map所有操作都是基于key-value对，而不是单独的元素。

下面以HashMap为例子，深入对Map的实现机制进行了解，在这个过程中，请打开jdk源码。

Hash算法

HashMap使用Hash算法，所以在解剖HashMap之间，需要先简单的了解Hash算法，Hash算法一般也成为散列算法，通过散列算法将任意的值转化成固定的长度输出，该输出就是散列值，这是一种压缩映射，也就是，散列值的空间远远小于输入的值空间。

简单的说，hash算法的意义在于提供了一种快速存取数据的方法,它用一种算法建立键值与真实值之间的对应关系,(每一个真实值只能有一个键值,但是一个键值可以对应多个真实值),这样可以快速在数组等里面存取数据。

下面我们建立一个HashMap,然后往里面放入12对key-value，这个HashMap的默认数组长度为16，我们的key分别存放在该数组的格子中，每个格子下面存放的元素又是以链表的方式存放元素。

public static void main(String[] args) { Map map = new HashMap(); map.put( " What " , " chenyz " ); map.put( " You " , " chenyz " ); map.put( " Dont " , " chenyz " ); map.put( " Know " , " chenyz " ); map.put( " About " , " chenyz " ); map.put( " Geo " , " chenyz " ); map.put( " APIs " , " chenyz " ); map.put( " Cant " , " chenyz " ); map.put( " Hurt " , " chenyz " ); map.put( " you " , " chenyz " ); map.put( " google " , " chenyz " ); map.put( " map " , " chenyz " ); map.put( " hello " , " chenyz " ); } 当我们新添加一个元素时，首先我们通过Hash算法计算出这个元素的Hash值的hashcode，通过这个hashcode的值，我们就可以计算出这个新元素应该存放在这个hash表的哪个格子里面，如果这个格子中已经存在元素，那么就把新的元素加入到已经存在格子元素的链表中。

运行上面的程序，我们对HashMap源码进行一点修改，打印出每个key对象的hash值

What-->hash值：8

You-->hash值：3

Dont-->hash值：7

Know-->hash值：13

About-->hash值：11

Geo-->hash值：12

APIs-->hash值：1

Cant-->hash值：7

Hurt-->hash值：1

you-->hash值：10

google-->hash值：3

map-->hash值：8

hello-->hash值：0

计算出来的Hash值分别代表该key应该存放在Hash表中对应数字的格子中，如果该格子已经有元素存在，那么该key就以链表的方式依次放入格子中

从上表可以看出，Hash表是线性表和链表的综合所得，根据数据结构的定义，可以得出粗劣的结论，Hash算法的存取速度要比数组差一些，但是比起单纯的链表，在查找和存取方面却要好多。

如果要查找一个元素时，同样的方式，通过Hash函数计算出这个元素的Hash值hashcode，然后通过这个hashcode值，直接找到跟这个hash值相对应的线性格子，进如该格子后，对这个格子存放的链表元素逐个进行比较，直到找到对应的hash值。

在简单了解完Hash算法后，我们打开HashMap源码

初始化HashMap

下面我们看看Map map = new HashMap();这段代码究竟做了什么，发生了什么数据结构的变化。

HashMap中几个重要的属性

transient Entry[] table;

用来保存key-value的对象Entry数组，也就是Hash表

transient int size;

返回HashMap的键值对个数

final float loadFactor;

负载因子，用来决定Entry数组是否扩容的因子，HashMap默认是0.75f

int threshold;

重构因子，(capacity * load factor)负载因子与Entry[]数组容积的乘值

public class HashMap < K,V > extends AbstractMap < K,V > implements Map < K,V > , Cloneable, Serializable { int threshold; final float loadFactor; transient Entry[] table; static final float DEFAULT_LOAD_FACTOR = 0.75f ; static final int DEFAULT_INITIAL_CAPACITY = 16 ; public HashMap( int initialCapacity, float loadFactor) { if (initialCapacity < 0 ) throw new IllegalArgumentException( " Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException( " Illegal load factor: " + loadFactor); // Find a power of 2 >= initialCapacity int capacity = 1 ; while (capacity < initialCapacity) capacity <<= 1 ; this .loadFactor = loadFactor; threshold = ( int )(capacity * loadFactor); table = new Entry[capacity]; init(); } 以public HashMap(int initialCapacity, float loadFactor)构造函数为例，另外两个构造函数实际上也是以同种方式来构建HashMap.

首先是要确定hashMap的初始化的长度，这里使用的策略是循环查出一个大于initialCapacity的2的次方的数，例如 initialCapacity的值是10，那么大于10的数是2的4次方，也就是16

capacity的值被赋予了16，那么实际上table数组的长度是16，之所以采用这样的策略来构建Hash表的长度，是因为2的次方运算对于计算机来说是有相当的效率。

loadFactor，

补充：软件开发 , Java ,