本来ArrayList和LinkedList弄完，应该去查看set接口的一些实现了，比如HashSet和TreeSet的实现了，但是看了下HashSet的底层存储是HashMap，所以决定先看HashMap的源码，看完再看HashSet的源码。

       HashMap是Map接口的一种实现，我们知道Map容器与Collection容器不一样，那Map是什么样的一种容器呢？

       Map是一种键值对容器（也称映射表或关联数组），基本思想是它维护的键--值关联，可以根据键查找出来值，像个字典一样，下面我们来看下HashMap是怎么实现Map容器的。

Map的接口函数：

1.HashMap定义

       hash其实就是散列的意思，（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做，存放记录的叫做。

       hashMap的定义如下：

public class HashMap
    
         extends AbstractMap
     
          implements Map
      
       , Cloneable, Serializable
      
     
    

可以看得到，HashMap继承了AbstractMap，实现了Map，Cloneable,Serializable接口。而AbstractMap实现了Map的一些基本方法。

2.HashMap的底层存储

//默认的初始化的容量，必须是2的倍数    static final int DEFAULT_INITIAL_CAPACITY = 16;      //最大的容量是2的30次方    static final int MAXIMUM_CAPACITY = 1 << 30;      //默认的加载因子，如果构造函数没有指定的话    static final float DEFAULT_LOAD_FACTOR = 0.75f;        //Entry表，长度必须是2的n次幂    transient Entry[] table;      //键值对的个数    transient int size;       //下次扩容的值（值为容量*加载因子）    int threshold;     //加载因子    final float loadFactor;

可以看出上面，HashMap定义了初始容量，最大容量，加载因子，存储下次要扩容的值，同时HashMap使用了Entry类型的数组存储据，那Entry是什么呢？

其实这个是一个内部类，代码如下：

static class Entry
    
      implements Map.Entry
     
       {        final K key; //键        V value;     //值        Entry
      
        next; //下一个节点        final int hash;              Entry(int h, K k, V v, Entry
       
         n) {            value = v;            next = n;            key = k;            hash = h;        }        //获取key        public final K getKey() {            return key;        }        //获取value        public final V getValue() {            return value;        }        //设置值        public final V setValue(V newValue) {	    V oldValue = value;            value = newValue;            return oldValue;        }        //判断两个节点释放相等，先判断key是不是相同，如果相同，在判断只是不是相等        public final boolean equals(Object o) {            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        public final int hashCode() {            return (key==null   ? 0 : key.hashCode()) ^                   (value==null ? 0 : value.hashCode());        }        public final String toString() {            return getKey() + "=" + getValue();        }        void recordAccess(HashMap
        
          m) {        }        void recordRemoval(HashMap
         
           m) { } }
         
        
       
      
     
    

可以看到Entry实现了Map里面的Entry接口，它定义了键(key)，值(value)，和下一个节点的引用(next)，以及hash值。

而Map里面的Entry接口代码如下：

interface Entry
    
      {    		K getKey();   	V getValue();	V setValue(V value);	boolean equals(Object o);	int hashCode();}
    

很明确的可以看出Entry是什么结构，它是单线链表的一个节点。也就是说HashMap的底层结构是一个数组，而数组的元素是一个单向链表。

        HashMap采用hash算法将key散列为一个int值，这个int值对应到数组的下标，再做查询操作的时候，拿到key的散列值，根据数组下标就能直接找到存储在数组的元素。但是由于hash可能会出现相同的散列值，为了解决冲突，HashMap采用将相同的散列值存储到一个链表中，也就是说在一个链表中的元素他们的散列值绝对是相同的。找到数组下标取出链表，再遍历链表这种方式比较高效，比直接使用数组存储键值对高效。

3.HashMap的构造函数

//根据初指定始化容量和加载因子来构造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        //初始值为1        int capacity = 1;        //如果小于，则capacity扩大2倍，一直循环到大于这个初始容量，因为数组的长度必须是2的幂次方        while (capacity < initialCapacity)            capacity <<= 1;        //赋值给加载因子        this.loadFactor = loadFactor;        //下次扩容的大小(其实就是扩容临界值)        threshold = (int)(capacity * loadFactor);        table = new Entry[capacity];        init();}//根据自定义容量来初始化HashMap,加载因子用默认的    public HashMap(int initialCapacity) {        this(initialCapacity, DEFAULT_LOAD_FACTOR);}//默认构造函数，初始化容量和加载因子都用默认的public HashMap() {        this.loadFactor = DEFAULT_LOAD_FACTOR;（0.75f）        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);        table = new Entry[DEFAULT_INITIAL_CAPACITY];(16)        init();}//构造一个指定map的HashMap。//先创建一个HashMap，容量去默认与指定容量的较大的一个，加载因子取默认的。public HashMap(Map
     m) {        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);        //然后将Map名为m的添加到刚才创建的HashMap里面去        putAllForCreate(m);}

最后一个构造函数使用putAllCreate的实现的增加，将下面查看下这个函数

private void putAllForCreate(Map
     m) {        //依次取出里面的元素        for (Iterator
    > i = m.entrySet().iterator(); i.hasNext(); ) {            Map.Entry
     e = i.next();            putForCreate(e.getKey(), e.getValue());        }} private void putForCreate(K key, V value) {        //计算出hash值        int hash = (key == null) ? 0 : hash(key.hashCode());        //计算出元素的index，是用hash值&table.length，所以最大值为table.length-1刚好是最后一个的下标        int i = indexFor(hash, table.length);        /**         * Look for preexisting entry for key.  This will never happen for         * clone or deserialize.  It will only happen for construction if the         * input Map is a sorted map whose ordering is inconsistent w/ equals.         */        //遍历hash表，找出hash相同的元素，取得该数组的下标，然后遍历该数组下标后面的链表，如果key也相同，则直接修改value为新值。        for (Entry
    
      e = table[i]; e != null; e = e.next) {            Object k;            if (e.hash == hash &&                ((k = e.key) == key || (key != null && key.equals(k)))) {                e.value = value;                return;            }        }        //表示以前的hash表没有存储，则添加进去        createEntry(hash, key, value, i);}//void createEntry(int hash, K key, V value, int bucketIndex) {	Entry
     
       e = table[bucketIndex];        table[bucketIndex] = new Entry
      
       (hash, key, value, e);        size++;}
      
     
    

4.增加

//根据指定的key和value来进行添加到HashMap里面public V put(K key, V value) {        //可以添加key为null的键值对        if (key == null)            return putForNullKey(value);        int hash = hash(key.hashCode());        int i = indexFor(hash, table.length);        for (Entry
    
      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++;        addEntry(hash, key, value, i);        return null;}//添加key值为null的键值对 private V putForNullKey(V value) {        //先循环遍历数组，看有没有key值为null的节点，有的话，将value换成行的value        for (Entry
     
       e = table[0]; e != null; e = e.next) {            if (e.key == null) {                V oldValue = e.value;                e.value = value;                e.recordAccess(this);                return oldValue;            }        }        modCount++;        //如果没有的话，则将其添加该数组下标为0的地方。        addEntry(0, null, value, 0);        return null;}void addEntry(int hash, K key, V value, int bucketIndex) {	Entry
      
        e = table[bucketIndex];        table[bucketIndex] = new Entry
       
        (hash, key, value, e);        //如果加入后的值大于或等于要扩容的临界值，就进行扩容        if (size++ >= threshold)            //长度为原来长度的两倍            resize(2 * table.length);} void resize(int newCapacity) {        Entry[] oldTable = table;        int oldCapacity = oldTable.length;        //如果HashMap的容量已经等于最大的HashMap允许的容量，则下次扩容为最大的Integer值，然后返回        if (oldCapacity == MAXIMUM_CAPACITY) {            threshold = Integer.MAX_VALUE;            return;        }        //创建一个扩容后的空的新Entry数组        Entry[] newTable = new Entry[newCapacity];        transfer(newTable);        table = newTable;        threshold = (int)(newCapacity * loadFactor);}//将老的HashMap的值，循环的添加进来void transfer(Entry[] newTable) {        Entry[] src = table;        int newCapacity = newTable.length;        //先循环取原来的Entry数组每一个元素        for (int j = 0; j < src.length; j++) {            //存储下该index节点的Entry节点，即该数组index链表的第一个节点            Entry
        
          e = src[j];            if (e != null) {                src[j] = null;//将原来的数组的index位置置为null，是为了让gc回收                do {                    //取到当前节点的下一个节点                    Entry
         
           next = e.next; //重新根据当前节点的hash值，计算该节点的位置 int i = indexFor(e.hash, newCapacity); //让e的下一个节点指向newTable e.next = newTable[i]; //将e放在这个index数组的位置上面 newTable[i] = e; //将当前节点移动到下一个节点 e = next; } while (e != null); } }}
         
        
       
      
     
    

所以如果执行了transfer，则数据的顺序就会变化。编程了相反的。

tranfer以后，变为：

       Map中的元素越多，hash冲突的几率也就越大，数组长度是固定的，所以导致链表越来越长，那么查询的效率当然也就越低下了。还记不记得同时数组容器的ArrayList怎么做的，扩容！而HashMap的扩容resize，需要将所有的元素重新计算后，一个个重新排列到新的数组中去，这是非常低效的，和ArrayList一样，在可以预知容量大小的情况下，提前预设容量会减少HashMap的扩容，提高性能。

　　再来看看加载因子的作用，如果加载因子越大，数组填充的越满，这样可以有效的利用空间，但是有一个弊端就是可能会导致冲突的加大，链表过长，反过来却又会造成内存空间的浪费。所以只能需要在空间和时间中找一个平衡点，那就是设置有效的加载因子。我们知道，很多时候为了提高查询效率的做法都是牺牲空间换取时间，到底该怎么取舍，那就要具体分析了。

5.删除

 

//根据Key删除元素，允许key值为nullpublic V remove(Object key) {    Entry
    
      e = removeEntryForKey(key);    return (e == null ? null : e.value);}//根据key来删除Map中的节点final Entry
     
       removeEntryForKey(Object key) {值        //计算出当前key的hash值        int hash = (key == null) ? 0 : hash(key.hashCode());        //根据hash值来计算index的位置        int i = indexFor(hash, table.length);        //将前一个阶段指向当前的index位置，要删除链表节点，就是要找到当前结点的钱一个节点，将前一个节点指向自己的后一个节点。这样就删除了。这个是pre的初始位置        Entry
      
        prev = table[i];        //当前结点也是index位置的数组节点        Entry
       
         e = prev;        while (e != null) {            //将当前结点的下一个位置记下来            Entry
        
          next = e.next;            Object k;            if (e.hash == hash &&                ((k = e.key) == key || (key != null && key.equals(k)))) {                modCount++;                size--;                //如果前一个节点当前结点是一个节点，表示第一个节点就是要删除的节点                if (prev == e)                    table[i] = next;                else//否则将当前结点的前一个节点指向自己的后一个节点。                    prev.next = next;                e.recordRemoval(this);                return e;            }            //将前一个节点指向当前结点            prev = e;            //当前结点指向后一个节点            e = next;        }        return e;}
        
       
      
     
    

6.修改

        我们看到HashMap并没有什么修改代码的接口，其实put就可以根据key,来修改值，因为key相同，如果再put，新的value会覆盖老的value。

7.查找

 

public V get(Object key) {        if (key == null)            return getForNullKey();        int hash = hash(key.hashCode());        for (Entry
    
      e = table[indexFor(hash, table.length)];             e != null;             e = e.next) {            Object k;            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))                return e.value;        }        return null;}private V getForNullKey() {        for (Entry
     
       e = table[0]; e != null; e = e.next) {            if (e.key == null)                return e.value;        }        return null;}
     
    

　从删除和查找可以看出，在根据key查找元素的时候，还是需要通过遍历，但是由于已经通过hash对key散列，要遍历的只是发生冲突后生成的链表，这样遍历的结果就已经少很多了，比我们自己写的完全遍历效率提升了n被。

8.其余的HashMap的操作

8.1 查找元素是否在容器中

public boolean containsKey(Object key) {        return getEntry(key) != null;}final Entry
    
      getEntry(Object key) {        int hash = (key == null) ? 0 : hash(key.hashCode());        for (Entry
     
       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;} public boolean containsValue(Object value) {	if (value == null)            return containsNullValue();	Entry[] tab = table;        for (int i = 0; i < tab.length ; i++)            for (Entry e = tab[i] ; e != null ; e = e.next)                if (value.equals(e.value))                    return true;	return false; }   private boolean containsNullValue() {	Entry[] tab = table;        for (int i = 0; i < tab.length ; i++)            for (Entry e = tab[i] ; e != null ; e = e.next)                if (e.value == null)                    return true;	return false;    }
     
    

 

基本常用的总结完毕，主要是看底层的数据结构，和其增删改查的算法实现。打完收工！