HashMap 主要用来存放键值对，它基于哈希表的Map接口实现，是常用的Java集合之一。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。

HashMap简介

HashMap是开发中使用频率最高的用于映射（键值对 key value）处理的数据结构，我们经常把hashMap数据结构叫做散列链表；

ObjectI entry<Key,Value>,entry<Key,Value>] 可以将数据通过键值对形式存起来

特点

HashMap根据键的hashcode值存储数据，大多数情况可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序是不确定的

想要使得遍历的顺序就是插入的顺序，可以使用LinkedHashMap，LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

publicclass HashMapTest {publicstaticvoidmain(String[] args) { HashMap hashMap =newHashMap(); hashMap.put(2,"bbb"); hashMap.put(3,"ccc"); hashMap.put(1,"aaa"); System.out.println("HashMap的遍历顺序："+hashMap); LinkedHashMap linkedHashMap =newLinkedHashMap(); linkedHashMap.put(2,"bbb"); linkedHashMap.put(3,"ccc"); linkedHashMap.put(1,"aaa"); System.out.println("LinkedHashMap的遍历顺序："+linkedHashMap); }}HashMap的遍历顺序：{1=aaa,2=bbb,3=ccc}LinkedHashMap的遍历顺序：{2=bbb,3=ccc,1=aaa}

线程不安全的HashMap

因为多线程环境下，使用Hashmap进行put操作会引起死循环，导致CPU利用率接近100%，所以在并发情况下不能使用HashMap。

HashMap最多只允许一条记录的键为null，允许多条记录的值为null

HashMap非线程安全，如果需要满足线程安全，可以一个Collections的synchronizedMap方法使HashMap具有线程安全能力，或者使用 ConcurrentHashMap

效率低下的HashTable容器

HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法时，其他线程访问HashTable的同步方法时，可能会进入阻塞或轮询状态。如线程1使用put进行添加元素，线程2不但不能使用put方法添加元素，并且也不能使用get方法来获取元素，所以竞争越激烈效率越低。

ConcurrentHashMap的锁分段技术

HashTable容器在竞争激烈的并发环境下表现出效率低下的原因，是因为所有访问HashTable的线程都必须竞争同一把锁，那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

通常会见到数据库优化，具体就是索引优化，那什么是索引优化呢？

举个例子，微信通讯录，最右侧会有a-z的排序，这就是索引，把数据分组，用到了hashMap数据结构

为什么键一个set集合，值是一个value集合

publicabstractclassAbstractMapimplementsMap{Setkeyset;Collectionvaluescollection;set数据结构：元素不能相同collection数据结构：元素可以相同因为在hashMap中，key（键）不能相同，value（值）是可以相同的

HashMap源码分析

核心成员变量

transientHashMapEntry[] table;//键值对的数组，存着每一个键值对transientHashMapEntryentryForNullKey;//没有键的键值对privatetransientSet> entrySet;//HashMap将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。transientintsize;//HashMap中实际存在的Node数量，注意这个数量不等于table的长度，甚至可能大于它，因为在table的每个节点上是一个链表（或RBT）结构，可能不止有一个Node元素存在。transientintmodCount;//HashMap的数据被修改的次数，这个变量用于迭代过程中的Fail-Fast机制，其存在的意义在于保证发生了线程安全问题时，能及时的发现（操作前备份的count和当前modCount不相等）并抛出异常终止操作。privatetransientintthreshold;//HashMap的扩容阈值，在HashMap中存储的键值对超过这个数量时，自动扩容容量为原来的二倍。finalfloatloadFactor;//HashMap的负载因子，可计算出当前table长度下的扩容阈值：threshold = loadFactor * table.length。

hashMap常量

privatestaticfinalintMINIMUM_cAPACITY =4;//最小容量privatestaticfinalintMAXIAMM_CAPACITY =1<<30;//最大容量，即2的30次方 （左移乘2，右移除2）staticfinalfloatDEFAULT_LOAD_FACTOR =0.75f;//加载因子，用于扩容，容量达到三分之二时，就准备扩容了staticfinalintMIN_TREEIFY_CAPACITY =64;//默认的最小的扩容量64，为避免重新扩容冲突，至少为4 * TREEIFY_THRESHOLD=32，即默认初始容量的2倍privatestaticfinalEntry[] EMPTY_TABLE =newHashMapEntry[MINIMUM CARACITY >>>1];//键值对数组最小容量（空的时候）

构造方法

//空参构造，使用默认的加载因子0.75publicHashMap(){this.loadFactor = DEFAULT_LOAD_FACTOR;  }//设置初始容量，并使用默认的加载因子publicHashMap(intinitialCapacity){this(initialCapacity, DEFAULT_LOAD_FACTOR); }//设置初始容量和加载因子，publicHashMap(intinitialCapacity,floatloadFactor){if(initialCapacity <0)thrownewIllegalArgumentException("Illegal initial capacity: "+ initialCapacity);if(initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY;if(loadFactor <=0|| Float.isNaN(loadFactor))thrownewIllegalArgumentException("Illegal load factor: "+ loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity); }

常用方法

publicinterfaceMap{}publicstaticinterfaceEntry>entryset();//获取实体集合publicSetkeyset();//获取键的集合publicSetValueset();//获取值的集合publicVput(K key,V vale);//往里面添加一个键值对publicvoidputAll(Mapmap);//添加一个键值对的、小的mappublicVremove(Object key);//通过一个键移除一个值publicintsize();//键值对的数量publicCollectignvalues();//值的集合

什么是HASH

是根据文件的内容的数据 通过逻辑运算得到的数值, 不同的文件(即使是相同的文件名)得到的HASH值是不同的, 所以HASH值就成了每一个文件在EMULE里的身份证.

secondary : 第二的table:存储键值对的数组tab.lenth=下标最大值e：tab[index] : 一维数组第一个元素，整个链表的头结点

put方法

下 1 代表下一个代码块有此方法 下下 2 代表下下一个代码块有此方法 依次类推

@Overridepublic V put(kkey, V value) { if (key== null) { return putValueForNu1lKey(value);//放一个空key的值 注：hashMap的值是可以为空的} int hash = Collections.下下2secondaryHash(key);//首先拿到键的hash值，这个key传进来之后进行两次hash：先拿到下 key.hashCode()本身hash值，再把它作为参数（object key）传进来，就是二次hash目的：为了不能key一直在一个数据域里，要分散一些，均匀排列，在0-9下下下1HashMapEntry[] tab = table;//为了安全问题声明局部变量tabint index = hash & (tab.length -1);//通过计算hash值再进行一个与运算，获取下标要放在哪个地方。 就相当于微信索引，计算出所在位置，打个比方，成--c，放在c区域里 一个区域可以有多个键只需要两行代码，就能找到key（n）所在的散列，　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　比如有10个链表，之前需要查10次，现在只需要查10分之1次，效率提高10倍，再通过迭代找具体元素，100个链表效率就提高100倍 for (HashMapEntry e = tab[index]; e！ = null; e = e.next) {//遍历整个下标下面整个链表，e：头结点 ，如果头结点不等于空，就让头结点等于他的下一个结点if (e.hash == hash &&key.equals(e.key)) {//键值对里的hash等于算出来的hash ，然后发现放进来的这个key和链表里的这个key相同，就覆盖preModify(e);覆盖 V oldValue = e.value;//以前的值oldValue赋值给新的valuee.value = value; return oldValue; } }　　　　　　modCount++;//找不到计数+1　　　　　　if(size++ > threshold){//数量有大小，也就是size，如果size++大于容量因子极限，就扩充tab = doubleCapacity();//容量乘以2，扩大两倍。最小是4，22 23 24 25 26 . . .index = hash &(tab.1ength-1);//扩完容再重新计算一遍下标的值}　　　　　　　　　　　　　　addNewEntry(key, value, hash, index); 　　　　　　return nul1; }public static int ①secondaryHash(Objectkey){　　return ②secondaryHash(key. hashCode());//先获取key本身的hashcode，再经过一次hash，调用secondaryHash}private static int 上上2secondaryHash(int h) { h += (h <<15) ^0xffffcd7d; h ^= (h >>>10); h += (h <<3); h ^= (h >>>6); h += (h <<2) + (h <<14); return h ^ (h >>>16);}

hashMap不仅仅是一种单纯的一维数组，有键key，有值value，还有next指针，这样的好处是 HashMap根据键的hashcode值存储数据，大多数情况可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序是不确定的

static class 上上上1HashMapEntry<K, V> implements Entry<K, V> {

final K key;

V value;

final int hash;

HashMapEntry<K, V> next; //如果出现相同的键，就通过这个指针指向下一个

HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {

this.key = key;

this.value = value;

this.hash = hash;

this.next = next;

　　}

oldCapacity：扩容之前的长度

newTable：

private HashMapEntry<K,V>[] doubleCapacity(){

　　HashMapEntry<K,V>[] oldTable=table; 　　//作为局部变量赋值

　　int oldCapacity =oldTable.1engtth;

　　if(oldCapacity == MAXTMUM_CAPACITY){ //现在的长度就等于最大就不扩容了

　　　　return oldTable;

}

　　int newCapacity = oldCapacity*2; 　　　　//否则，扩容2倍

　　HashMapEntry<K,V>[] newTable = makeTable(newCapacity); //声明了一个newTable，让他的长度等于newCapacity

if(size==0){ 　　　　　　　　　　　　　　　　//没元素在里面

　　　　return newTable;

}

　 for(int j=Q;j<b1dcapacity;j++){ 　　　　//遍历，为了把老数组里的元素放到新数组里面来

　　　　 HashMapEntry<K,V>e=oldTable[j]; 　　//拿到老的数组里的每一个键值对

　　　 　if(e==nul1){

　　　　 　　continue;

　　　　 }　　//键值对为空，则不管

　　　　int highBit=e. hash & oldCapacity; //拿到键值对里的hash和oldCapacity长度，进行取小（highBit）

　　　　HashMapEntry<K,V>broken=null;

　　　　newTable[j | highBit]=e; 　　　//把highBit放在newTable里面，和j进行一个或运算，其实就是把元素丢到新的里面来

　　　　for(HashMapEntry<K,V>n=e. next;n!=null;e=n,n=n. next){ //把串里的数据全部拿出来，重新计算下标

　　　　　　int nextHighBit=n. hash & oldCapacity;

　　　　　　if(nextHighBit!=highBit){ 　　　　 //如果后面子串和前面这个串，计算出来的下标不同，不能再放在这个数组（相当于微信的一个索引）里了

　　　　　　　　if(broken==null) 　　　　　　　 //不相等

　　　　　　　　　　newTable[j | nextHighBit]=n; //应该放在newTable新的下标去 或运算的时候分成两个区间

　　　　　　　　else

　　　　　　　　　　broken.next = n; 　　　　　　　 //如果相等，放在next后面，继续串起来

　　　　　　　　broken=e;

　　　　　　　　heigBit = nextHighBit；

　　　　　　}

　　　　}

　　　　if(broken !=null)

　　　　　　broken. next=null;

　　　　　　}

　　　　return newTable;

　　}

table[index] = next 也就是链表中下一个元素

table[index]就相当于微信同一个索引下的某个元素，有两个了，再添加，就用next指向下一个元素

串只需要用头结点来表示，要做到是先把新结点连接到串里面来，然后再让tab[index]等于这个串，这个串本身就是这个头结点，比如现在有三个串（头结点也有一个），新进来的串放在前面

void addNewEntry(K key,V value,int hash,int index){

table[index]=new HashMapEntry<K,V>(key,value,hash,table[index]（next指针）); 蓝色为新结点，放在tab[index]里面来，就是头结点，相当于新结点变成了头结点，

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　而新结点作为头结点的next指针，作为一个引用引进来了

，这个图就是，tab[index]这个一维数组中的某个元素或存储区域，让它等于新加进来的元素--newHashMap，让新进来的元素的next指针指向tab[index]

remove

tab[index]：头结点

prev=null 默认为空

@overridepublic V remove(objectkey) {　　if (key==null) {　　　　return removeNullke();//移除空键但有值的键值对}inthash = Collections.secondaryHash(key); 　　HashMapEntry[] tab = table;intindex = hash & (tab.length -1); 　　for (HashMapEntry e = tab[index],prev=null;//遍历串里的每一个元素，让头结点等于ee !=null;prev= e, e = e.next){//让头结点e等于prev，又让e.next(头结点的下一个元素等于e)二次遍历　　　　if (e.hash == hash &&key.equals(e.key)) { hash相等，又能equals，说明找到了这个结点　　　　　　if (prev==null) {　　　　　　　　tab[index] = e.next; 让头结点不再等于之前的prev，把e放在头结点位置，然后e.next就是tab[index]（头结点），成功上位了哈哈　　　　　　} else {prev.next= e.next;prev.next不指向下一个元素了，指向下一个的下一个（e.next），就表示把e删除了　　　　　　modCount++;　　　　　　size++;

要删除一个key1，找到下标索引就是index=0 第一列，但是这个index=0有很多键值对，不能直接把index=0里的所有键值对删除吧，所以要先查找找出来，删除需要的键值对

修改元素：

元素的修改也是put方法，因为key是唯一的，所以修改元素，是把新值覆盖旧值。

第一排，只有最后4位才有效，因为与运算全是1才为1，所以 0000=1001=0(最小值) 1001+1001=9（最大值）

hash%10也是(0~9)，因为hash不固定

与运算lenth-1均匀的分布成0~9 或运算分成两个区间

hash相同 key不一定相同>> key1 key2产生的hash很有可能是相同的，如果key真的相同，就不会存在散列链表了，散列链表是很多不同的键算出的hash值和index相同的

key相同 经过两次hash hash一定相同

tips

想理解数据结构源码，得理清楚当一个新的元素被添加进来以后，会和之前的老的元素产生什么关系

首先看继承的关系，看成员变量，看元素之间的关系，看元素之间的关系就是在添加元素的时候，这组元素和之前的元素有什么关系，put方法

总结：不必对每个不同的对象都产生一个唯一的hashcode，只要HashCode方法使get()能够得到put()放进去的内容就可以。生成hashcode的算法尽量使hashcode的值分散一些，不要许多hashcode都集中在一个范围内，这样有利于提高HashMap的性能。