https://blog.csdn.net/u010575093/article/details/50731281

抽象类中可以定义成员变量，而接口中定义的成员变量实际上都是常量

接口不可继承抽象类，抽象类可实现多个接口。接口与接口之间是继承，用extends，可继承多个接口
mport java.util.HashMap;
import java.util.Map;

interface Test{
        public void mm();
}

interface Test1{
        public void kk();
}
//接口可以继承多个接口
interface Test2 extends Test, Test1{
        public void mk();
}
//抽象类成员都是public，
//抽象类中可以定义成员变量，而接口中定义的成员变量实际上都是常量。
//抽象类可以继承接口,并实现接口方法
abstract class ATest1 implements Test1{
        public void kk(){  System.out.println("ATtest mm");  }
}

abstract class ATest2 implements Test1, Test{
        public void mm(){       System.out.println("ATest2 mm");        }
        public void kk(){}
}
// 抽象类可以继承抽象类 也可以继承实体类
abstract class ATest3 extends ATest1{

}

class Solution{
	//时间复杂度n
        public void tosum(int[] nums, int target){
                Map<Integer, Integer> map = new HashMap<>();
                for(int i = 0; i < nums.length; i++)
                        map.put(nums[i],i);
                for(int i = 0; i < nums.length; i++){
                        int comp = target - nums[i];
                        System.out.println("comp="+comp+" containsKey "+map.containsKey(comp));
                        System.out.println("map get "+map.get(comp));
                        if(map.containsKey(comp) && map.get(comp)!=i){
                                System.out.println("match:"+i+" "+map.get(comp));
                        }
                }
                System.out.println("tosum");
        }
        //时间复杂度1
        public int[] tosum1(int[] nums, int target){
                Map<Integer, Integer> map = new HashMap<>();
                for (int i = 0; i < nums.length; i++) {
                        int complement = target - nums[i];
                        if (map.containsKey(complement)) {
                                return new int[] { map.get(complement), i };
                        }
                        map.put(nums[i], i);
                }
                throw new IllegalArgumentException("No two sum solution");
        }
}
class HashSum{

        public static void main(String argv[]){
                System.out.println("111");
                new Solution().tosum();
        }
}

                                      java中HashMap原理

内推军P21 P22

1、为什么用HashMap？

HashMap是一个散列桶（数组和链表），它存储的内容是键值对(key-value)映射HashMap采用了数组和链表的数据结构，能在查询和修改方便继承了数组的线性查找和链表的寻址修改HashMap是非synchronized，所以HashMap很快HashMap可以接受null键和值，而Hashtable则不能（原因就是equlas()方法需要对象，因为HashMap是后出的API经过处理才可以）

2、HashMap的工作原理是什么？

HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，计算并返回的hashCode是用于找到Map数组的bucket位置来储存Node 对象。这里关键点在于指出，HashMap是在bucket中储存键对象和值对象，作为Map.Node 。



put过程（JDK1.8版）

1、对Key求Hash值，然后再计算下标

2、如果没有碰撞，直接放入桶中（碰撞的意思是计算得到的Hash值相同，需要放到同一个bucket中）

3、如果碰撞了，以链表的方式链接到后面

4、如果链表长度超过阀值( TREEIFY THRESHOLD==8)，就把链表转成红黑树，链表长度低于6，就把红黑树转回链表

5、如果节点已经存在就替换旧值

6、如果桶满了(容量16*加载因子0.75)，就需要 resize（扩容2倍后重排）

get过程(考虑特殊情况如果两个键的hashcode相同，你如何获取值对象？)

当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。

3、有什么方法可以减少碰撞？

扰动函数可以减少碰撞，原理是如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这就意味着存链表结构减小，这样取值的话就不会频繁调用equal方法，这样就能提高HashMap的性能。（扰动即Hash方法内部的算法实现，目的是让不同对象返回不同hashcode。）

使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择。为什么String, Interger这样的wrapper类适合作为键？因为String是final的，而且已经重写了equals()和hashCode()方法了。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。

4 HashMap中hash函数怎么是是实现的?

我们可以看到在hashmap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合，所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。 所以我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，能不能找一种更快速，消耗更小的方式，我们来看看JDK1.8的源码是怎么做的

1 static final int hash(Object key) {if (key == null){ return 0; } int h; h=key.hashCode()；返回散列值也就是hashcode

2 ^ ：按位异或 // >>>:无符号右移，忽略符号位，空位都以0补齐

3其中n是数组的长度，即Map的数组部分初始化长度 return (n-1)&(h ^ (h >>> 16));



简单来说就是

1、高16bt不变，低16bit和高16bit做了一个异或(得到的HASHCODE转化为32位的二进制，前16位和后16位低16bit和高16bit做了一个异或)

2、(n·1)&hash=->得到下标

5 拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？

之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

6解决hash 碰撞还有那些办法？

开放定址法。

当冲突发生时，使用某种探查技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的地址。

按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。

问题：已知一组关键字为(26，36，41，38，44，15，68，12，06，51)，用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表。

解答：为了减少冲突，通常令装填因子α由除余法因子是13的散列函数计算出的上述关键字序列的散列地址为(0，10，2，12，5，2，3，12，6，12)。

前5个关键字插入时，其相应的地址均为开放地址，故将它们直接插入T[0]，T[10)，T[2]，T[12]和T[5]中。

当插入第6个关键字15时，其散列地址2(即h(15)=15％13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)％13=3，此地址开放，所以将15放入T[3]中。

当插入第7个关键字68时，其散列地址3已被非同义词15先占用，故将其插入到T[4]中。

当插入第8个关键字12时，散列地址12已被同义词38占用，故探查hl=(12+1)％13=0，而T[0]亦被26占用，再探查h2=(12+2)％13=1，此地址开放，可将12插入其中。

类似地，第9个关键字06直接插入T[6]中；而最后一个关键字51插人时，因探查的地址12，0，1，…，6均非空，故51插入T[7]中。

7 如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。这个值只可能在两个地方，一个是原下标的位置，另一种是在下标为<原下标+原容量>的位置

8 重新调整HashMap大小存在什么问题吗？

当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。(多线程的环境下不使用HashMap）

为什么多线程会导致死循环，它是怎么发生的？

HashMap的容量是有限的。当经过多次元素插入，使得HashMap达到一定饱和度时，Key映射位置发生冲突的几率会逐渐提高。这时候，HashMap需要扩展它的长度，也就是进行Resize。1.扩容：创建一个新的Entry空数组，长度是原数组的2倍。2.ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。

图示

1 正常的ReHash的过程

我假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。

最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table[1]这里了。

接下来的三个步骤是Hash表 resize成4，然后所有的<key,value> 重新rehash的过程



2 并发下的Rehash

1）假设我们有两个线程。我用红色和浅蓝色标注了一下。

我们再回头看一下我们的 transfer代码中的这个细节：
do {
    Entry<K,V> next = e.next; // <--假设线程一执行到这里就被调度挂起了
    int i = indexFor(e.hash, newCapacity);
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
} while (e != null);
而我们的线程二执行完成了。于是我们有下面的这个样子。




注意，因为Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。

2）线程一被调度回来执行。

先是执行 newTalbe[i] = e;

然后是e = next，导致了e指向了key(7)，

而下一次循环的next = e.next导致了next指向了key(3)



3）一切安好。

线程一接着工作。把key(7)摘下来，放到newTable[i]的第一个，然后把e和next往下移。



4）环形链接出现。

e.next = newTable[i] 导致  key(3).next 指向了 key(7)

注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。

 



于是，当我们的线程一调用到，HashTable.get(11)时，悲剧就出现了——Infinite Loop。

9 HashMap的rehash源代码

1 Put一个Key,Value对到Hash表中：

public V put(K key, V value)
{
    ......
    //算Hash值
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    //如果该key已被插入，则替换掉旧的value （链接操作）
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //该key不存在，需要增加一个结点
    addEntry(hash, key, value, i);
    return null;
}


2 检查容量是否超标

void addEntry(int hash, K key, V value, int bucketIndex)
{
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    //查看当前的size是否超过了我们设定的阈值threshold，如果超过，需要resize
    if (size++ >= threshold)
        resize(2 * table.length);
}


3新建一个更大尺寸的hash表，然后把数据从老的Hash表中迁移到新的Hash表中。

void resize(int newCapacity)
{
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    ......
    //创建一个新的Hash Table
    Entry[] newTable = new Entry[newCapacity];
    //将Old Hash Table上的数据迁移到New Hash Table上
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}


4 迁移的源代码，注意高亮处：

void transfer(Entry[] newTable)
{
    Entry[] src = table;
    int newCapacity = newTable.length;
    //下面这段代码的意思是：
    //  从OldTable里摘一个元素出来，然后放到NewTable中
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}


5 如何选择线程安全的容器？

Java编码中，我们经常需要用到容器来编程。在并发环境下，Java提供一些已有容器能够支持并发。

1.Map



在Map类中，提供两种线程安全容器。

java.util.Hashtable

Hashtable和HashMap类似，都是散列表，存储键值对映射。主要区别在于Hashtable是线程安全的。当我们查看Hashtable源码的时候，可以看到Hashtable的方法都是通过synchronized来进行方法层次的同步，以达到线程安全的作用。

java.util.concurrent.ConcurrentHashMap

ConcurrentHashMap是性能更好的散列表。在兼顾线程安全的同时，相对于Hashtable，在效率上有很大的提高。我们可以猜想，Hashtable的线程安全实现是对方法进行synchronized，很明显可以通过其他并发方式，如ReentrantLock进行优化。而ConcurrentHashMap正是采用了ReentrantLock。运用锁分离技术，即在代码块上加锁，而不是方法上加。同时ConcurrentHashMap的一个特色是允许多个修改并发操作。这就有意思了，我们知道一般写都是互斥的，为什么这个还能多个同时写呢？那是因为ConcurrentHashMap采用了内部使用段机制，将ConcurrentHashMap分成了很多小段。只要不在一个小段上写就可以并发写。

具体看内推军P22

2 Collection



Collection部分主要是运用的CopyOnWrite机制，即写时复制机制。从字面上就能理解什么意思，就是当我们往一个容器里添加元素的时候，先对这个容器进行一次复制，对副本进行写操作。写操作结束后，将原容器的引用指向新副本容器，就完成了写的刷新。

从它的实现原理，我们可以看出这种机制是存在缺点的。

1.内存占用：毫无疑问，每次写时需要首先复制一遍原容器，假如复制了很多，或者本身原容器就比较大，那么肯定会占用很多内存。可以采用压缩容器中的元素来防止内存消耗过大。

2.数据一致性问题：当我们在副本中进行写操组时，只能在最终结束后使数据同步，不能实时同步

可以看到，这种机制适用于读操作多，写操作少的应用场景。

java.util.concurrent.CopyOnWriteArrayList

Collection类的线程安全容器主要都是利用的ReentrantLock实现的线程安全，CopyOnWriteArrayList也不例外。在并发写的时候，需要获取lock。读的时候不需要进行lock

java.util.concurrent.CopyOnWriteArraySet

CopyOnWriteArraySet的实现就是基于CopyOnWriteArrayList实现的，采用的装饰器进行实现。二者的区别和List和Set的区别一样。

Vector

一般我们都不用Vector了，不过它确实也是线程安全的。相对于其他容器，能够提供随机访问功能。

 

StringBuffer和StringBuilder



我们知道，String在进行+操作的时候，原生的String会重新新建一个String对象来完成字符串拼接，明显这种操作多了的话会加重服务器负担。因此我们需要的时候就会用StringBuffer和StringBuilder。这二者有什么区别呢？

StringBuffer是线程安全的，StringBuilder不是。从StringBuffer的源码可以看到，它采用的是对方法进行synchronized实现的同步。但是加了同步机制，肯定会对性能有一定影响。

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。
HashMap 实现了 Map 接口，根据键的 HashCode 值存储数据，具有很快的访问速度，最多允许一条记录的键为 null，不支持线程同步。
HashMap 是无序的，即不会记录插入的顺序。
HashMap 继承于AbstractMap，实现了 Map、Cloneable、java.io.Serializable 接口。

HashMap类常用操作




方法
功能
描述




put()
将键/值对添加到 hashMap 中



get()
获取指定 key 对应对 value



getOrDefault()
获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值



remove()
删除指定键 key 的映射关系



containsKey()
是否存在指定的 key



keySet()
返回 hashMap 中所有 key 组成的集合视图。



values()
返回 hashMap 中存在的所有 value 值。



isEmpty()
判断 hashMap 是否为空



size()
计算 hashMap 中键/值对的数量



forEach()
对 hashMap 中的每个映射执行指定的操作。



containsValue()
检查 hashMap 中是否存在指定的 value 对应的映射关系。



HashMap与Hashtable的抉择
HashMap和Hashtable都实现了Map接口，都是键值对保存数据的方式
区别1：

HashMap可以存放 null
Hashtable不能存放null

区别2：

HashMap不是线程安全的类
Hashtable是线程安全的类

目录 

 1. HashMap简介 

 2. HashMap的底层结构 

 3. HashMap源码分析 

 4. HashMap的扩容机制 

 5. HashMap的性能



1、HashMap简介

HashMap是一个用于存储（key-value）结构的散列表
,继承了AbstractMap，实现了Map、Cloneable、java.io.Serializable 3个接口
HashMap的key和value都是可以为null的 
HashMap是线程不安全的，如果在高并发情况下想要保证线程安全，可以考虑使用HashTable或者currentHashMap。
currentHashMap效率会比HashTable高。
2、HashMap的底层结构

HashMap底层数据结构是数组+链表
其能够有相当快的查询速度（时间复杂度为O(1) ）是因为对key的hashcode 使用hash算法进行运算，得出存储在数组中的下标  
如果储存的对象一旦多起来了，就有可能导致hash冲突，即数组下标重复 。HashMap为了解决这个问题，采用了链表的结构  
如果最新插入的Entry 的数组下标中已经存有数据了，则把该位置让出来给新插入的Entry并让其指向上一个Entry节点。




3、HashMap源码（jdk1.7）



3.1主要属性

DEFAULT_LOAD_FACTOR （加载因子），当加载因子越小的时候，数组利用率会越低，HashMap的hash冲突就会越低，即entry链表长度越短，查找效率越高。反之，加载因子越大，数组利用率会越高，HashMap的hash冲突就会越多，即entry链表长度越长，查找效率越低。



    //存储entry数组的默认初始容量 ，为2的4次方
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    //默认的最大容量 为2的30次方
    static final int MAXIMUM_CAPACITY = 1 << 30;

    //默认加载因子，数组使用率到达75%的时候就扩容
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //当数组表还没扩容的时候，一个共享的空表对象
    static final Entry<?,?>[] EMPTY_TABLE = {};

    //内部数组，用来装entry，大小只能是2的n次方。
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

    //存储Entry<K,V>的个数
    transient int size;

    /**
     * 扩容的临界点（加载因子*数组容量），如果当前容量达到该值，则需要扩容了。
     * 如果当前数组容量为0时（空数组），则该值作为初始化内部数组的初始容量
     */
    int threshold;

    //构造函数传进来的加载因子
    final float loadFactor;

    //Hash被修改的次数
    transient int modCount;

    //threshold的最大值
    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

    //计算hash值时候用，初始是0
    transient int hashSeed = 0;

    //含有所有entry节点的一个set集合
    private transient Set<Map.Entry<K,V>> entrySet = null;



3.2 Entry类分析

Entry

static class Entry<K,V> implements Map.Entry<K,V> {

        final K key;

        V value;
        //多个Entry是构成单向链表结构，数组中存储的是一个个entry所构成的链表，next是指向下一个entry节点
        Entry<K,V> next;
        //用于记录本entry节点的hash值
        int hash;

        //初始化节点
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
        //获取节点的key
        public final K getKey() {
            return key;
        }

        //获取节点的value
        public final V getValue() {
            return value;
        }

        //设置新value，并返回旧的value
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        //判断传入节点与此结点是否相等，如果相等则返回true，反之返回false
        public final boolean equals(Object o) {
            //传入对象不是Entry，就返回false
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        //根据key和value生成hashCode
        public final int hashCode() {
            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

        //每当相同key的value被覆盖时被调用一次，在HashMap的子类LinkedHashMap中实现了这个方法
        void recordAccess(HashMap<K,V> m) {
        }

        //每移除一个entry就被调用一次，在HashMap的子类LinkedHashMap中实现了这个方法；
        void recordRemoval(HashMap<K,V> m) {
        }
    }



3.3 构造器分析

HashMap调用构造方法的时候，参数为非具体值并不会创建容器。当传具体值的时候，会创建一个内部数组（table数组）。默认初始容量是16，在3.1主要属性 中的代码块中有所体现，字段为DEFAULT_INITIAL_CAPACITY。



    /**
     * 生成一个空HashMap，传入容量与加载因子
     * @param initialCapacity 初始容量
     * @param loadFactor 加载因子
     */
    public HashMap(int initialCapacity, float loadFactor) {
        //初始容量不能小于0
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        //初始容量不能大于默认的最大容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;

        //加载因子不能小于0，且不能为NaN(Not a Number)
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                    loadFactor);
        //把加载因子赋值给属性
        this.loadFactor = loadFactor;
        //设置临界值
        threshold = initialCapacity;
        //该方法只在LinkedHashMap中有实现，主要在构造函数初始化和clone、readObject中有调用。
        init();
    }

    /**
     * 生成一个空hashmap，传入初始容量，加载因子使用默认值（0.75）
     * @param initialCapacity 初始容量
     */
    public HashMap(int initialCapacity) {
        //生成空数组，并指定扩容值
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 根据已有map对象生成一个hashmap，初始容量与传入的map相关，加载因子使用默认值
     * @param m Map对象
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        //生成空数组，并指定扩容值
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);

        //由于此时数组为空，所以使用“扩容临界值”新建一个数组
        inflateTable(threshold);

        //将传入map的键值对添加到初始数组中
        putAllForCreate(m);
    }



3.4 存储分析(put)

put方法和get方法是HashMap中最常用的方法，下面对put方法进行分析。 
如果key为null的话，hash值为0，对象存储在table中index为0的位置(table[0])。当K不为null时，会先计算出K的hash值，然后通过hash值与table的length映射出一个下标i，这个i就是Entry存放在数组的位置。然后遍历table[i]的Entry，如果有相同K的，就替换新的value，返回oldvalue，结束。反之把新的Entry插入链表头部。



put算法流程图如下





put源码



 /**
     * 存入一个键值对，如果key重复，则更新value
     * @param key 键值名
     * @param value 键值
     * @return 如果存的是新key则返回null，如果覆盖了旧键值对，则返回旧value
     */
    public V put(K key, V value) {
        //如果数组为空，则新建数组
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }

        //如果key为null，则把value放在table[0]中
        if (key == null)
            return putForNullKey(value);

        //生成key所对应的hash值
        int hash = hash(key);

        //根据hash值和数组的长度找到：该key所属entry在table中的位置i
        int i = indexFor(hash, table.length);

        /**
         * 先找到i位置，然后遍历entry，
         * 如果发现存在key与传入key相等，则替换其value。返回oldvalue
         * 如果没有找到相同的key，则继续执行下一条指令，将此键值对存入链表头
         */
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //map操作次数加一
        modCount++;
        //扩容检测和添加entry
        addEntry(hash, key, value, i);
        return null;
    }



3.5获取源码分析（get）

下面是put的分析

get方法用于获取出入的参数Key所对应的value，get方法会先对key进行判断，如果为null就执行getForNullKey()，否则就通过getEntry()来找到entry，再通过entry获取value。其中getForNullKey()和getEntry()的算法流程如下








    /**
     * 根据key找到对应value
     * @param key 键值名
     * @return 键值value
     */
    public V get(Object key) {
        //如果key为null，则从table[0]中取value
        if (key == null)
            return getForNullKey();

        //如果key不为null，则先根据key，找到其entry
        Entry<K,V> entry = getEntry(key);

        //返回entry节点里的value值
        return null == entry ? null : entry.getValue();
    }

 private V getForNullKey() {
        if (size == 0) {
            return null;
        }
        //查找table[0]处的链表，如果找到entry的key为null，就返回其value
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

    /**
     * 根据key值查找所属entry节点
     * @param key 键值名
     * @return entry节点
     */
    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        //如果key为null，则其hash值为0，否则计算hash值
        int hash = (key == null) ? 0 : hash(key);

        //根据hash值找到table下标，然后迭代该下标中的链表里的每一个entry节点
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            //如果找到该节点则返回该节点
            if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }




4、HashMap的扩容机制

当HashMap存储的元素越来越多的时候，hash冲突就会越来越多，查询效率就会越来越低。因为定位到table[i]的时候，需要遍历table[i]中的链表，冲突越多，链表的长度就会越长，所以查询的效率就越慢。为了提高效率，就需要对table进行扩容处理，也就是进行resize()，resize（）这个操作也会出现在ArrayList中。

言归正传，resize是HashMap中最消耗性能的一个操作，在resize中，原数组中的所有数据会重新计算一次其在新数组中的位置，并存放进去。当HashMap在进行put操作的时候，检测到table的使用量达到扩容的临界threshold 的时候，就会进行扩容操作（threshold= table.length * DEFAULT_LOAD_FACTOR）



 /**
     * 对数组扩容，即创建一个新数组，并将旧数组里的东西重新存入新数组
     * @param newCapacity 新数组容量
     */
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;

        //如果当前数组容量已经达到最大值了，则将扩容的临界值设置为Integer.MAX_VALUE(Integer.MAX_VALUE是容量的临界点)
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        //创建一个扩容后的新数组
        Entry[] newTable = new Entry[newCapacity];

        //将当前数组中的键值对存入新数组
        transfer(newTable, initHashSeedAsNeeded(newCapacity));

        //用新数组替换旧数组
        table = newTable;

        //计算下一个扩容临界点
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    /**
     * 将现有数组中的内容重新通过hash计算存入新数组
     * @param newTable 新数组
     * @param rehash
     */
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;

        //遍历现有数组中的链表
        for (Entry<K,V> e : table) {
            //查找链表里的每一个entry
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }

                //根据新的数组长度，重新计算此entry所在下标i
                int i = indexFor(e.hash, newCapacity);

                //将新的entry插入链表头部
                e.next = newTable[i];
                newTable[i] = e;

                //查看下一个entry
                e = next;
            }
        }
    }



5、HashMap性能

HashMap中，加载因子是衡量的是一个散列表的空间的使用程度，加载因子越大表示散列表的使用率越高，HashMap的hash冲突就会越多，即entry链表长度越长，查找效率越低。当加载因子越小的时候，数组利用率会越低，HashMap的hash冲突就会越少，即entry链表长度越短，查找效率越高。HashMap查找一个元素的效率为O(1+avg(entry.length))，即O(1)。经研究发现，加载因子选取0.75是比较合适的



PS:博文中如有什么不对的地方恳请大家指出，谢谢~