从上表可以看出，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.75fint threshold;重构因子，(capacity * load factor)负载因子与Entry[]数组容积的乘值publicclassHashMap<K,V>extendsAbstractMap<K,V>implementsMap<K,V>,Cloneable,Serializable{intthreshold;finalfloatloadFactor;transientEntry[]table;staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;staticfinalintDEFAULT_INITIAL_CAPACITY=16;publicHashMap(intinitialCapacity,floatloadFactor){if(initialCapacity<0)thrownewIllegalArgumentException("Illegalinitialcapacity:"+initialCapacity);if(initialCapacity>MAXIMUM_CAPACITY)initialCapacity=MAXIMUM_CAPACITY;if(loadFactor<=0||Float.isNaN(loadFactor))thrownewIllegalArgumentException("Illegalloadfactor:"+loadFactor);//Findapowerof2>=initialCapacityintcapacity=1;while(capacity<initialCapacity)capacity<<=1;this.loadFactor=loadFactor;threshold=(int)(capacity*loadFactor);table=newEntry[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，被称为负载因子，HashMap的默认负载因子是0.75fthreshold，接下来是重构因子，由负载因子和容量的乘机组成，它表示当HashMap元素被存放了多少个之后，需要对HashMap进行重构。通过这一系列的计算和定义后，初始化Entry[] table;put(key,value)接下来看一对key-value是如何被存放到HashMap中：put(key,value)publicVput(Kkey,Vvalue){if(key==null)returnputForNullKey(value);inthash=hash(key.hashCode());inti=indexFor(hash,table.length);System.out.PRintln(key+"-->hash值："+i);//这就是刚才程序打印出来的key对应hash值for(Entry<K,V>e=table[i];e!=null;e=e.next){Objectk;if(e.hash==hash&&((k=e.key)==key||key.equals(k))){VoldValue=e.value;e.value=value;e.recordaccess(this);returnoldValue;}}modCount++;addEntry(hash,key,value,i);returnnull;}staticinthash(inth){h^=(h>>>20)^(h>>>12);returnh^(h>>>7)^(h>>>4);}staticintindexFor(inth,intlength){returnh&(length-1);}这里是整个hash的关键，请打开源码查看一步一步查看。hash(key.hashCode())计算出key的hash码 //对于hash()的算法，这里有一篇分析很透彻的文章<HashMap hash方法分析>indexFor(hash, table.length)通过一个与算法计算出来，该key应在存放在Hash表的哪个格子中。for (Entry<K,V> e = table[i]; e != null; e = e.next)然后再遍历table[i]格中的链表，判断是否已经存在一样的key，如果存在一样的key值，那么就用新的value覆盖旧的value，并把旧的value值返回。addEntry(hash, key, value, i)如果经过遍历链表没有发现同样的key，那么进行addEntry函数的操作，增加当前key到hash表中的第i个格子中的链表中voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){Entry<K,V>e=table[bucketIndex];table[bucketIndex]=newEntry<K,V>(hash,key,value,e);if(size++>=threshold)resize(2*table.length);}Entry<K,V> e = table[bucketIndex]; 创建一个Entry对象来存放键值（ps:Entry对象是一个链表对象）table[bucketIndex] = new Entry<K,V>(hash, key, value, e);将Entry对象添加到链表中if (size++ >= threshold) resize(2 * table.length);最后将size进行自增，判断size值是否大于重构因子，如果大于那么就是用resize进行扩容重构。voidresize(intnewCapacity){Entry[]oldTable=table;intoldCapacity=oldTable.length;if(oldCapacity==MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;return;}Entry[]newTable=newEntry[newCapacity];transfer(newTable);table=newTable;threshold=(int)(newCapacity*loadFactor);}这里为什么是否需要扩容重构，其实是涉及到负载因子的性能问题loadFactor负载因子上面说过loadFactor是一个hashMap的决定性属性，HashSet和HashMap的默认负载因子都是0.75，它表示，如果哈希表的容量超过3/4时，将自动成倍的增加哈希表的容量，这个值是权衡了时间和空间的成本，如果负载因子较高，虽然会减少对内存空间的需求，但也会增加查找数据的时间开销，无论是put()和get()都涉及到对数据进行查找的动作，所以负载因子是不适宜设置过高
get(key)接下来看看get(key)做了什么publicVget(Objectkey){if(key==null)returngetForNullKey();inthash=hash(key.hashCode());for(Entry<K,V>e=table[indexFor(hash,table.length)];e!=null;e=e.next){Objectk;if(e.hash==hash&&((k=e.key)==key||key.equals(k)))returne.value;}returnnull;}这些动作似乎是跟put(key，value)相识，通过hash算法获取key的hash码，再通过indexFor定位出该key存在于table的哪一个下表，获取该下标然后对下标中的链表进行遍历比对，如果有符合就直接返回该key的value值。keySet()这里还涉及另一个问题，上面说了HashMap是跟set没有任何亲属关系，但map也一样实现了keySet接口，下面谱析一下keySet在hashMap中是如何实现的，这里给出部分代码，请结合源码查看publicKnext(){returnnextEntry().getKey();}finalEntry<K,V>nextEntry(){if(modCount!=expectedModCount)thrownewConcurrentModificationException();Entry<K,V>e=next;if(e==null)thrownewNoSuchElementException();if((next=e.next)==null){Entry[]t=table;while(index<t.length&&(next=t[index++])==null);}current=e;returne;}代码很简单，就是对每个格子里面的链表进行遍历，也正是这个原因，当我们依次将key值put进hashMap中，但在使用map.entrySet().iterator()进行遍历时候却不是put时候的顺序。扩容在前面说到put函数的时候，已经提过了扩容的问题if(size++>=threshold)resize(2*table.length);这里一个是否扩容的判断，当数据达到了threshold所谓的重构因子，而不是HashMap的最大容量，就进行扩容。voidresize(intnewCapacity){Entry[]oldTable=table;intoldCapacity=oldTable.length;if(oldCapacity==MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;return;}Entry[]newTable=newEntry[newCapacity];transfer(newTable);table=newTable;threshold=(int)(newCapacity*loadFactor);}voidtransfer(Entry[]newTable){Entry[]src=table;intnewCapacity=newTable.length;for(intj=0;j<src.length;j++){Entry<K,V>e=src[j];if(e!=null){src[j]=null;do{Entry<K,V>next=e.next;inti=indexFor(e.hash,newCapacity);e.next=newTable[i];newTable[i]=e;e=next;}while(e!=null);}}}transfer方法实际上是将所有的元素重新进行一些hash，这是因为容量变化了，每个元素相对应的hash值也会不一样。使用HashMap1.不要再高并发中使用HashMap，HashMap是线程不安全，如果被多个线程共享之后，将可能发生不可预知的问题。2.如果数据大小事固定的，最好在初始化的时候就给HashMap一个合理的容量值，如果使用new HashMap()默认构造函数，重构因子的值是16*0.75=12，当HashMap的容量超过了12后，就会进行一系列的扩容运算，重建一个原来成倍的数组，并且对原来存在的元素进行重新的hash运算，如果你的数据是有成千上万的，那么你的成千上万的数据也要跟这你的扩容不断的hash，这将产生高额的内存和cpu的大量开销。当然啦，HashMap的函数还有很多，不过都是基于table的链表进行操作，当然也就是hash算法，Map & hashMap在平时我们的应用非常多，最重要的是我们要对每句代码中每块数据结构变化心中有数。上面主要是参考了jdk源码，数据结构和一些相关资料本着好记性不如烂博客的精神记录下来，希望朋友们如果发觉哪里不对请指出来，虚心请教新闻热点
疑难解答
