HashMap底层就是一个数组结构,HashMap中key与value都

作者: 编程  发布:2019-10-09

Map是映射表的实现,是关联数组,维护着键与值的关联关系,因此可以根据键找到对应的值。

本文基于JDK1.7,HashTable是用同步来实现线程安全的Map,使用Hash算法定位,与HashMap类似,HashMap是线程不安全的,单线程下效率更高,多线程下ConcurrentHashMap可保证线程安全且效率优于HashTable

继续深入Java基础系列。今天是研究下哈希表,毕竟我们很多应用层的查找存储框架都是哈希作为它的根数据结构进行封装的嘛。

一、HashMap

9159.com 1

Hashtable 概要

与HashMap主要区别是Hashtable的put,get方法都是同步的,线程安全,但是性能较差 key和value都不能为null,HashMap中key与value都可以为 null 与HashMap类似,key必须实现hashCode()和equals方法,由于equals判断前都会先判断hashCode方法是否相等,两个equals的对象的hashCode()必须相同,否则在put等方法中不会覆盖 与HashMap类似,capacity和loadFactor是影响其性能的两个关键参数。capacity代表桶的个数,初始化initialcapacity为较大值可以减少扩容(rehash,transfer)开销,但是初始消耗更多空间,且增大了遍历时间(与capacity和size成正比,没有元素的数组点也需要遍历)开销。loadFactor代表其空间时间性能交换权衡系数,loadFactor默认为0.75,调大该系数使得空间利用率提高,但是get和put方法的时间性能降低。 与HashMap类似,其实现基于数组,用开放定址法解决Hash冲突,每个数组点存储一个链表,当元素个数size>capacity*loadFactor时进行扩容 Hashtable迭代器以及其集合视图(keySet,values)的迭代器都具有fail-fast机制,迭代器被创建后,所有除了迭代器外对集合结构性(插入,删除,更新不是结构修改)的修改都会抛出异常。迭代器通过检查modCount来判断是否在迭代过程中出现了结构性的修改。 Hashtable是线程安全的,其线程安全是基于同步的,如果不需要线程安全建议使用HashMap,如果需要高并发,建议使用ConcurrentHashMap

本系列:

1.HashMap概述:

Java中有几种不同的Map实现,体现了各自不同的优势,或者是注重查找性能的HashMap、或者注重线程安全的ConcurrentHashMap,亦或Key有序排列的TreeMap等等。

Hashtable 类头部

Hashtable继承Dictionary,而HashMap继承AbstractMap。Dictionary只是提供了虚函数,没有实现任何方法,AbstractMap实现了丰富的方法,如:equals,toString等。 HashMap与Hashtable实现的其他接口都是一样的

public class Hashtable
    extends Dictionary
    implements Map, Cloneable, java.io.Serializable {  
public class HashMap
    extends AbstractMap
    implements Map, Cloneable, Serializable  

(1)深入Java基础(一)——基本数据类型及其包装类

HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

而本节要讲的正是HashMap,是基于散列表的实现,插入和查询“键值对”操作具有近似O的时间复杂度,并提供了通过调整容量负载因子的手段来优化Map的性能。

主要成员变量

table数组用来存储元素链表 count计数元素个数 threshold 扩容的阈值 loadFactor 扩容因子,控制扩容时机(capacity*loadFactor

    private transient Entry[] table;
    private transient int count;
    private int threshold;
    private float loadFactor;
    private transient int modCount = 0; 
    transient int hashSeed; 

(2)深入Java基础(二)——字符串家族

2.HashMap的数据结构:

HashMap的实现是数组+链表,很是简单,本文就不够多赘述,而是侧重从工程实践出发,陈述些HashMap使用的注意点或容易忽视且容易想当然的出错点。

构造方法

根据initialCapacity,loadFactor,创建table数组,计算threshold 根据Map初始化,首先创建二倍于原Map size的table数组,将原有元素transfer到新table中,该过程是同步的 与HashMap不同,其容量capacity并不是2的幂次

    public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);
        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        initHashSeedAsNeeded(initialCapacity);
    }  
    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }
    public Hashtable() {
        this(11, 0.75f);
    }
    public Hashtable(Map t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }  
    public synchronized void putAll(Map t) {
        for (Map.Entry e : t.entrySet())
            put(e.getKey(), e.getValue());
    }  

(3)深入Java基础(三)--集合(1)集合父类以及父接口源码及理解

在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针,所有的数据结构都可以用这两个基本结构来构造,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。如下图,HashMap底层就是一个数组结构,数组中的每一项又是一个链表。当新建一个HashMap的时候,就会初始化一个数组。

null的处理

编程中,最长见的异常,就有NPE(NullPointerException ),那么HashMap是如何处理key或者value为null的情况呢?

在HashMap中 ,Key是用来定位数组索引的,若Key为Null,则索引为0,也就是说键值对会放到数组的第一个桶位,若被占据,则链表链接,插入的逻辑和非null一模一样。

插入其实就是寻找位置的过程,此过程value不起任何作用。但是如果使用putIfAbsent()方法,就有需要注意的地方了。如果仅从字面上理解,可能会认为,如果通过key查找不到相等的元素,就插入新元素,反之,则不插入。其实不然,此方法解读应该是:元素不存在则作为新元素插入,当元素存在但是value==null时,也替换value值。

 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; }

基本节点 Entry

clone为浅拷贝,没有创建key和value 单链表节点除了保存key和value外,还保存了指向下一节点的指针next 有hash值域

    private static class Entry implements Map.Entry {
        int hash;
        final K key;
        V value;
        Entry next;
        protected Entry(int hash, K key, V value, Entry next) {
            this.hash = hash;
            this.key =  key;
            this.value = value;
            this.next = next;
        }
        protected Object clone() {
            return new Entry<>(hash, key, value,
                                  (next==null ? null : (Entry) next.clone()));
        }
        // set get方法
        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            return key.equals(e.getKey()) && value.equals(e.getValue());
        }
        public int hashCode() {
            return (Objects.hashCode(key) ^ Objects.hashCode(value));
        }
        public String toString() {
            return key.toString()+"="+value.toString();
        }
    }  

(4)深入Java基础(三)--集合(2)ArrayList和其继承树源码解析以及其注意事项


源码:

定位算法

HashMap中数组下标的计算并不是通过hash%length,而是(length - 1) & hash(两个数与计算,最终的结果肯定小于或者等于最小的那个值,最后肯定不越界)。这种方式明细不直观,不符合常规思维,难道是这种方式有更优的性能吗?

不妨用JMH微机准测试下:

 static int length = 32; @Benchmark public void wellHelloThere() { int i = RandomUtils.nextInt() % length; } @Benchmark public void wellHelloThere1() { int i = RandomUtils.nextInt() & (length - 1); } public static void main(String[] args) throws RunnerException { Options opt = new OptionsBuilder() .include(JMHTest.class.getSimpleName .forks .mode(Mode.Throughput) .warmupIterations .measurementIterations .build(); new Runner.run(); }

我的机器上执行,吞吐量ops几乎相等,这几乎可以排除性能的原因,那到底有何用意?下面详细分析。

Hashtable 中的Holder内部类

Holder用来加载当虚拟机完全启动后才初始化的因子 由于String类型的key的hashCode方法可能产生更多的hash碰撞,所以JDK7中设定了阈值,当超过阈值后使用一种特殊的hashCode计算方法,JDK1.8中已经去除相应机制 初始化hashSeed时,首先判断虚拟机是否完全启动,然后根据是否使用altHashing决定hashSeed的值

    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
    private static class Holder {  
        static final int ALTERNATIVE_HASHING_THRESHOLD;
        static {
            String altThreshold = java.security.AccessController.doPrivileged(
                new sun.security.action.GetPropertyAction(
                    "jdk.map.althashing.threshold"));
            int threshold;
            try {
                threshold = (null != altThreshold)
                        ? Integer.parseInt(altThreshold)
                        : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
                // disable alternative hashing if -1
                if (threshold == -1) {
                    threshold = Integer.MAX_VALUE;
                }
                if (threshold < 0) {
                    throw new IllegalArgumentException("value must be positive integer.");
                }
            } catch(IllegalArgumentException failed) {
                throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
            }
            ALTERNATIVE_HASHING_THRESHOLD = threshold;
        }
    }  
    final boolean initHashSeedAsNeeded(int capacity) {
        boolean currentAltHashing = hashSeed != 0;
        boolean useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean switching = currentAltHashing ^ useAltHashing;
        if (switching) {
            hashSeed = useAltHashing
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;
        }
        return switching;
    }  

文章结构:(1)哈希概述及HashMap应用;(2)HashMap源码分析;(3)再次总结关键点


/**

数组扩容

HashMap有两个重要的属性,容量和负载因子。容量为数组的长度,而负载因子是一个衡量什么时候数组扩容的指标,默认值为0.75。

数组容量负载因子计算出的扩容阈值Threshold是最终的度量,当Map中元素数量大于Threshold时,此时HashMap需要实例化新数组然后把老Map的元素放到新的Map中,可以肯定,这个过程是整个HashMap中最耗时的,涉及所有元素的位置调整。

元素转移最简单的思路可能就是将所有的元素重新调用put方法,这会重新hash计算,定位桶位,遍历链表,有严重的性能问题,那么实际的操作又是怎样的呢?

HashMap底层数组长度始终是2的次方,不管你初始化设置数组容量为多少,例如:赋值为7,实际则是8,赋值为17,则为32。

下图展示扩容重新下标计算:

9159.com 2

所有,只需要把原数组每个节点的链表按照高位是否为1进行拆分为2个链表,高位为1的链接到新的位置,也就是(原位置+原数组长度),为0的链接到新数组中原来的位置。

从而得出结论,(length - 1) & hash的算法选择是为了降低扩容时的性能损耗考虑的。

插入元素 put方法

与HashMap最大的区别在于整个put方法是被synchronized包围的,整个方法是同步的 计算key的hash值,如果使用alternative hashing还需要与hashSeed进行抑或,进一步打乱 与Integer.maxvalue按位与,确保hash值为正的,对table.length取余计算index值 table.index位置可能已有元素(产生hash碰撞),采用头插法,将元素插入到index位置的头部 如果元素个数超过threshold,进行扩容(rehash()),扩容至原来的2倍多一的大小 由于table.length变化,index需要重新计算 将原table中的元素transfer到新的table中,将头插法添加新元素

注意(e.hash == hash) && e.key.equals(key)在判断是插入还是更新时,先判断hash值是否相等,如果hash值不等,即便equals返回true也会执行插入操作,而不是更新操作

    public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }
        // Makes sure the key is not already in the hashtable.
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }
        modCount++;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();
            tab = table;
            hash = hash(key);
            index = (hash & 0x7FFFFFFF) % tab.length;
        }
        // Creates the new entry.
        Entry e = tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        return null;
    }  
    private int hash(Object k) {
        // hashSeed will be zero if alternative hashing is disabled.
        return hashSeed ^ k.hashCode();
    }  
    protected void rehash() {
        int oldCapacity = table.length;
        Entry[] oldMap = table;
        // overflow-conscious code
        int newCapacity = (oldCapacity << 1) + 1;
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        Entry[] newMap = new Entry[newCapacity];
        modCount++;
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        boolean rehash = initHashSeedAsNeeded(newCapacity);
        table = newMap;
        for (int i = oldCapacity ; i-- > 0 ;) {
            for (Entry old = oldMap[i] ; old != null ; ) {
                Entry e = old;
                old = old.next;
                if (rehash) {
                    e.hash = hash(e.key);
                }
                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = newMap[index];
                newMap[index] = e;
            }
        }
    }  

一、哈希概述及HashMap应用:

* The table, resized as necessary. Length MUST Always be a power of two.

初始容量和负载因子对性能的影响

当HashMap元素数量达到阈值,rehashing就会发生,频繁的发生会造成很大的开销。选择合适的初始容量将会很大程度上减少rehashing的发生,会改善HashMap的写入性能。

凡是有两面性,如果容量很大,且元素很少时,迭代操作将会产生额外的开销,所以当需要经常的进行迭代操作,就需要节点分布适当的紧促了,也就是说初始容量不能过大。

过大的负载因子会减少空间的使用,但会造成查询(包括get和put)的耗时增加,默认值0.75是考虑了空间成本和时间成本后的一种折中方案,是一权衡。如果过小,也会造成迭代操作的消耗增加。

HashMap是非线程安全的,多线程访问时如果有一个线程是写操作,则需要进行外部同步操作,否则其他线程将观察到对象内部的不一致状态,或者写入操作根本就不能被其他线程看见。

在多线程环境下,应该使用同步的Map,最好使用ConcurrentHashMap,而不是包装 Collections.synchronizedMap(new HashMap以及Hashtable。

fail-fast

如同其他的非并发容器一样,HashMap的遍历也是快速失败机制,当iterator被创建后,任何对于底层数据结构的改变(put,remove)都可能会导致 ConcurrentModificationException异常的产生,由于没有使用同步,所有异常并不是一定会产生,这只是提供一种定位bug的参考。

Hashtable是线程安全的,而HashMap并不是,在单线程环境下HashMap性能更优,毕竟锁是有开销的。

Hashtable不允许key或者value为null,HashMap则可以。

以上大概就是实际使用中需要了解,也需要注意的点了,为了代码的健壮,理解原理还是必要的。

查询方法 get

定位到table指定位置,然后顺链表查找 注意get方法也是同步的,在put方法执行完之前,get方法也需要等待

    public synchronized V get(Object key) {
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return e.value;
            }
        }
        return null;
    }  

概述:详细介绍

*/

查找算法 containsKey containsValue

查询方法也是同步的,需要等待put方法执行完 对key的查询可以用hash算法直接定位到table数组指定的位置 对value的查询,需要遍历整个table数组和所有链表节点,因此时间复杂度是与(capacity和size)成正比

    public synchronized boolean containsKey(Object key) {
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return true;
            }
        }
        return false;
    }  
    public boolean containsValue(Object value) {
        return contains(value);
    }  
    public synchronized boolean contains(Object value) {
        if (value == null) {
            throw new NullPointerException();
        }
        Entry tab[] = table;
        for (int i = tab.length ; i-- > 0 ;) {
            for (Entry e = tab[i] ; e != null ; e = e.next) {
                if (e.value.equals(value)) {
                    return true;
                }
            }
        }
        return false;
    }  

根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。

transient Entry[] table;

删除

首先定位到table指定位置 注意删除对应位置头结点时的情况

    public synchronized V remove(Object key) {
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                modCount++;
                if (prev != null) {
                    prev.next = e.next;
                } else {
                    tab[index] = e.next;
                }
                count--;
                V oldValue = e.value;
                e.value = null;
                return oldValue;
            }
        }
        return null;
    }  
对比:数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。哈希则是一种寻址容易,插入删除也容易的数据结构。

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

浅拷贝 clone

由于没有对key和value进行克隆,所以当通过原map修改key和value的属性时,新map中的key和value也会改变 与HashMap不同的是HashMap为对每个节点重建了Entry(同样没有克隆key和value),HashTable只是重建了table中的每个头结点

    public synchronized Object clone() {
        try {
            Hashtable t = (Hashtable) super.clone();
            t.table = new Entry[table.length];
            for (int i = table.length ; i-- > 0 ; ) {
                t.table[i] = (table[i] != null)
                    ? (Entry) table[i].clone() : null;
            }
            t.keySet = null;
            t.entrySet = null;
            t.values = null;
            t.modCount = 0;
            return t;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError();
        }
    }  

实际应用:

final K key;

视图 KeySet ValueSet EntrySet

视图是针对于HashTable 的table 进行的操作,与通过HashTable操作效果相同 与HashMap不同,contains,remove方法又重新写了一遍,而在HashMap中是直接调用的HashMap的已有方法,HashMap中的实现更简洁

    private class EntrySet extends AbstractSet> {
        public Iterator> iterator() {
            return getIterator(ENTRIES);
        }
        public boolean add(Map.Entry o) {
            return super.add(o);
        }
        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry entry = (Map.Entry)o;
            Object key = entry.getKey();
            Entry[] tab = table;
            int hash = hash(key);
            int index = (hash & 0x7FFFFFFF) % tab.length;
            for (Entry e = tab[index]; e != null; e = e.next)
                if (e.hash==hash && e.equals(entry))
                    return true;
            return false;
        }
        public boolean remove(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry entry = (Map.Entry) o;
            K key = entry.getKey();
            Entry[] tab = table;
            int hash = hash(key);
            int index = (hash & 0x7FFFFFFF) % tab.length;
            for (Entry e = tab[index], prev = null; e != null;
                 prev = e, e = e.next) {
                if (e.hash==hash && e.equals(entry)) {
                    modCount++;
                    if (prev != null)
                        prev.next = e.next;
                    else
                        tab[index] = e.next;
                    count--;
                    e.value = null;
                    return true;
                }
            }
            return false;
        }
        public int size() {
            return count;
        }
        public void clear() {
            Hashtable.this.clear();
        }
    }  
1.Hash主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值. 也可以说,Hash就是找到一种数据内容和数据存放地址之间的映射关系

V value;

迭代器

由于rehash等因素,迭代次序并不保证不变 查找下一个元素算法:如果当前链表已经到尾节点,从数组中顺次查找下一个非空节点,头结点作为next() 通过模拟枚举变量KEYS,VALUES,ENTRYS,同时实现了三种视图的Iterator Enumerator是已经被废弃的迭代元素的方法,相比于Iterator他缺少了remove方法,且方法名更长 Hashtable同时对这两种接口进行了适配

    private class Enumerator implements Enumeration, Iterator {
        Entry[] table = Hashtable.this.table;
        int index = table.length;
        Entry entry = null;
        Entry lastReturned = null;
        int type;
        /**
         * Indicates whether this Enumerator is serving as an Iterator
         * or an Enumeration.  (true -> Iterator).
         */
        boolean iterator;
        /**
         * The modCount value that the iterator believes that the backing
         * Hashtable should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        protected int expectedModCount = modCount;
        Enumerator(int type, boolean iterator) {
            this.type = type;
            this.iterator = iterator;
        }
        public boolean hasMoreElements() {
            Entry e = entry;
            int i = index;
            Entry[] t = table;
            /* Use locals for faster loop iteration */
            while (e == null && i > 0) {
                e = t[--i];
            }
            entry = e;
            index = i;
            return e != null;
        }
        public T nextElement() {
            Entry et = entry;
            int i = index;
            Entry[] t = table;
            /* Use locals for faster loop iteration */
            while (et == null && i > 0) {
                et = t[--i];
            }
            entry = et;
            index = i;
            if (et != null) {
                Entry e = lastReturned = entry;
                entry = e.next;
                return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
            }
            throw new NoSuchElementException("Hashtable Enumerator");
        }
        // Iterator methods
        public boolean hasNext() {
            return hasMoreElements();
        }
        public T next() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            return nextElement();
        }
        public void remove() {
            if (!iterator)
                throw new UnsupportedOperationException();
            if (lastReturned == null)
                throw new IllegalStateException("Hashtable Enumerator");
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            synchronized(Hashtable.this) {
                Entry[] tab = Hashtable.this.table;
                int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
                for (Entry e = tab[index], prev = null; e != null;
                     prev = e, e = e.next) {
                    if (e == lastReturned) {
                        modCount++;
                        expectedModCount++;
                        if (prev == null)
                            tab[index] = e.next;
                        else
                            prev.next = e.next;
                        count--;
                        lastReturned = null;
                        return;
                    }
                }
                throw new ConcurrentModificationException();
            }
        }
    }  
2.查找:哈希表,又称为散列,是一种更加快捷的查找技术。我们之前的查找,都是这样一种思路:集合中拿出来一个元素,看看是否与我们要找的相等,如果不等,缩小范围,继续查找。而哈希表是完全另外一种思路:当我知道key值以后,我就可以直接计算出这个元素在集合中的位置,根本不需要一次又一次的查找!

Entry<K,V> next;

序列化

与HashMap实现相同,key与value分别写出,在对端逐个读入Key和value,然后加入新Map进行关联 由于count在可以传输得到,所以预先确定了table的容量,减少了扩容的开销

    private void writeObject(java.io.ObjectOutputStream s)
            throws IOException {
        Entry entryStack = null;
        synchronized (this) {
            // Write out the length, threshold, loadfactor
            s.defaultWriteObject();
            // Write out length, count of elements
            s.writeInt(table.length);
            s.writeInt(count);
            // Stack copies of the entries in the table
            for (int index = 0; index < table.length; index++) {
                Entry entry = table[index];
                while (entry != null) {
                    entryStack =
                        new Entry<>(0, entry.key, entry.value, entryStack);
                    entry = entry.next;
                }
            }
        }
        // Write out the key/value objects from the stacked entries
        while (entryStack != null) {
            s.writeObject(entryStack.key);
            s.writeObject(entryStack.value);
            entryStack = entryStack.next;
        }
    }
    private void readObject(java.io.ObjectInputStream s)
         throws IOException, ClassNotFoundException
    {
        // Read in the length, threshold, and loadfactor
        s.defaultReadObject();
        // Read the original length of the array and number of elements
        int origlength = s.readInt();
        int elements = s.readInt();
        // Compute new size with a bit of room 5% to grow but
        // no larger than the original size.  Make the length
        // odd if it's large enough, this helps distribute the entries.
        // Guard against the length ending up zero, that's not valid.
        int length = (int)(elements * loadFactor) + (elements / 20) + 3;
        if (length > elements && (length & 1) == 0)
            length--;
        if (origlength > 0 && length > origlength)
            length = origlength;
        Entry[] newTable = new Entry[length];
        threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
        count = 0;
        initHashSeedAsNeeded(length);
        // Read the number of elements and then all the key/value objects
        for (; elements > 0; elements--) {
            K key = (K)s.readObject();
            V value = (V)s.readObject();
            // synch could be eliminated for performance
            reconstitutionPut(newTable, key, value);
        }
        this.table = newTable;
    }  

HashMap概述:

final int hash;

Hash表 是一种逻辑数据结构,HashMap是Java中的一种数据类型(结构类型),它通过代码实现了Hash表 这种数据结构,并在此结构上定义了一系列操作。

……

HashMap关键点罗列:

}

1.基于数组来实现哈希表的,数组就好比内存储空间,数组的index就好比内存的地址;

Entry就是数组中的元素,每个Map.Entry其实就是一个Key-Value对,它持有一个指向下一个元素的引用,这就构成了链表。

2.每个记录就是一个Entry 《K, V>对象,数组中存储的就是这些对象;

3.HashMap的存储实现:

3.HashMap的哈希函数 = 计算出hashCode + 计算出数组的index;

public V put(K key, V value) {

4.HashMap解决冲突:使用链地址法,每个Entry对象都有一个引用next来指向链表的下一个Entry;(也就是链地址法)

// HashMap允许存放null键和null值。

但是!JDK1.8升级了!!

// 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。

JDK1.8之前:使用单向链表来存储相同索引值的元素。在最坏的情况下,这种方式会将HashMap的get方法的性能从O(1)降低到O(n)。

if (key == null)

在JDK1.8:为了解决在频繁冲突时hashmap性能降低的问题,使用平衡树来替代链表存储冲突的元素。这意味着我们可以将最坏情况下的性能从O(n)提高到O(logn)。

return putForNullKey;

在Java 8中使用常量TREEIFY_THRESHOLD来控制是否切换到平衡树来存储。目前,这个常量值是8,这意味着当有超过8个元素的索引一样时,HashMap会使用树来存储它们。

// 根据key的keyCode重新计算hash值。

这一动态的特性使得HashMap一开始使用链表,并在冲突的元素数量超过指定值时用平衡二叉树替换链表。不过这一特性在所有基于hash table的类中并没有,例如Hashtable和WeakHashMap。目前,只有ConcurrentHashMap,LinkedHashMap和HashMap会在频繁冲突的情况下使用平衡树。

int hash = hash(key.hashCode;

5.装填因子:默认为0.75;

// 搜索指定hash值在对应table中的索引。

(加载因子过高虽然减少了空间开销,但同时也增加了查询成本(在大多数 HashMap 类的操作中,包括 get 和 put 操作,都反映了这一点)。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子,则不会发生 rehash 操作。)

int i = indexFor(hash, table.length);

6.继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接口。

这里写图片描述

// 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。

7.不是线程安全的。它的key、value都可以为null。此外,HashMap中的映射不是有序的。

for (Entry<K,V> e = table[i]; e != null; e = e.next) {

8.影响性能的因素:“初始容量” 和 “加载因子”

Object k;

容量 是哈希表中桶的数量,初始容量 只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。

if (e.hash == hash && ((k = e.key) == key || key.equals {

HashMap基本操作:

public class TestHashMap {
    public static void main(String[] args) {

        HashMap<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("fu", "辅助");
        hashMap.put("ad", "输出");
        hashMap.put("sd", "上单");

        System.out.println(hashMap);//toString重写了,所以可直接打出
        System.out.println("fu:" + hashMap.get("fu"));//拿出key为fu的键值
        System.out.println(hashMap.containsKey("fu"));//判断是否存在fu的键
        System.out.println(hashMap.keySet());//返回一个key集合。
        System.out.println("判空:"+hashMap.isEmpty());//判空

        hashMap.remove("fu");
        System.out.println(hashMap.containsKey("fu"));//判断是否存在fu的键

        Iterator it = hashMap.keySet().iterator();//遍历输出值。前提先拿到一个装载了key的Set集合
        while(it.hasNext()) {
            String key = (String)it.next();
            System.out.println("key:" + key);
            System.out.println("value:" + hashMap.get(key));
        }

    }
}

V oldValue = e.value;

二、HashTable重要的部分源码分析:(基于jdk1.8)

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    private static final long serialVersionUID = 362498820763181265L;
      // 默认的初始容量是16,必须是2的幂。 
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    // 最大容量(必须是2的幂且小于2的30次方,传入容量过大将被这个值替换) 
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认加载因子 
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //!!Java 8 HashMap的分离链表。 在没有降低哈希冲突的度的情况下,使用红黑书代替链表。
    /*
    使用链表还是树,与一个哈希桶中的元素数目有关。下面两个参数中展示了Java 8的HashMap在使用树和使用链表之间切换的阈值。当冲突的元素数增加到8时,链表变为树;当减少至6时,树切换为链表。中间有2个缓冲值的原因是避免频繁的切换浪费计算机资源。
    */
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;

//HashMap的一个内部类,实现了Map接口的内部接口Entry。Map接口的一系列方法
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;//哈希值
        final K key;
        V value;
        Node<K,V> next;//对下一个节点的引用(看到链表的内容,结合定义的Entry数组,哈希表的链地址法!!!实现)

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }//获取Key
        public final V getValue()      { return value; }//获取Value
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }
    // 存储数据的Node数组,长度是2的幂。    
    // HashMap采用链表法解决冲突,每一个Entry本质上是一个单向链表    
    transient Node<K,V>[] table;
    //缓存我们装载的Node,每个结点。这也是跟keySet一样,可用于遍历HashMap。遍历使用这个比keySet是快多的喔,一会介绍并给例子。
    transient Set<Map.Entry<K,V>> entrySet;
    // HashMap的底层数组中已用槽的数量    
    transient int size;  
    // HashMap被改变的次数   
    transient int modCount;
    // HashMap的阈值,用于判断是否需要调整HashMap的容量(threshold = 容量*加载因子)    
    int threshold;
    // 加载因子实际大小 
    final float loadFactor;

    /*
    构造器
    */
    public HashMap(int initialCapacity, float loadFactor) {
    //初始容量不能<0
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
     //初始容量不能 > 最大容量值,HashMap的最大容量值为2^30
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
     //负载因子不能 < 0
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
    //当在实例化HashMap实例时,如果给定了initialCapacity,由于HashMap的capacity都是2的幂,因此这个方法用于找到大于等于initialCapacity的最小的2的幂(initialCapacity如果就是2的幂,则返回的还是这个数)。 
     static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    //本质还是上面的构造器,只不过不选择加载因子而已
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    //这里更是两个都不选,都选取默认的大小。
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }     
    //这个大概了解就是,可以用Map来构造HashMap咯
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
    //那堆获取size,判空方法就不列了。
    // 获取key对应的value    
    public V get(Object key) {
        Node<K,V> e;
        // 获取key的hash值 
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab;
        Node<K,V> first, e; 
         int n; 
         K k;
         // 在“该hash值对应的链表”上查找“键值等于key”的元素。也就是取出这个链表上,索引对应的值。
         //这里一边判断一边赋值了,1.把要查的那一行table数组给到临时数组tab(那一行的table数组是通过hash计算得出的);2.把那一行的数组的第一个给到暂存结点first。(所谓第一个其实是单链表中头部,链表的头插法)    
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
             // 直接命中
            if (first.hash == hash && // 每次都是校验第一个node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
                // 未直接命中。
            if ((e = first.next) != null) {
            //如果已经变成红黑树存储方式了,当然用树的方式去查找。
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    // 遍历单链表,在链表中获取
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        //什么贵都没找到
        return null;
    }
    //红黑树查找法
    final TreeNode<K,V> getTreeNode(int h, Object k) {
            return ((parent != null) ? root() : this).find(h, k, null);
    }
     //根节点
    final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
    }
    /** 
     * 从根节点p开始查找指定hash值和关键字key的结点 
     * 当第一次使用比较器比较关键字时,参数kc储存了关键字key的 比较器类别 
     * 非递归式的树查询写法。。。有点复杂。
    */  
    final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
            TreeNode<K,V> p = this;//一开始是根节点,然后遍历下去,表示当前结点
            do {
                int ph, dir; K pk;
                TreeNode<K,V> pl = p.left, pr = p.right, q;
                if ((ph = p.hash) > h) //如果给定哈希值小于当前节点的哈希值,进入左节点  
                    p = pl;
                else if (ph < h)//如果大于当前节点,进入右结点  
                    p = pr;
                else if ((pk = p.key) == k || (k != null && k.equals(pk))) //如果哈希值相等,且关键字相等,则返回当前节点,终止查找。  
                    return p;
                else if (pl == null) //如果左节点为空,则进入右结点  
                    p = pr;
                else if (pr == null)//如果右结点为空,则进入左节点  
                    p = pl;
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0) //如果不按哈希值排序,而是按照比较器排序,则通过比较器返回值决定进入左右结点  
                    p = (dir < 0) ? pl : pr;
                else if ((q = pr.find(h, k, kc)) != null)//如果在右结点中找到该关键字,直接返回
                    return q;
                else
                    p = pl;  //进入左节点  
            } while (p != null);
            return null;
    }
    //同理推出是否包含某key的方法
    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }
    /*
    插入方法!!为了好理解,我们先去看下文讲的jdk1.7的put吧,这个jdk1.8的红黑树、链式的转换太复杂了,一会回来再看。
    */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; 
        Node<K,V> p;
        int n, i;
        //判断table是否为空
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;//创建一个新的table数组,用resize确定大小,并且获取该数组的长度
             //根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {//如果对应的节点存在
            Node<K,V> e; K k;
            //判断table[i]的首个元素是否和key一样,如果相同直接覆盖value
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
           //判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
          // 该链为链表,就用链地址法
            else {
            //遍历table[i],判断链表长度是否大于TREEIFY_THRESHOLD(默认值为8),大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //树转型
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
             // 写入覆盖
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
    /*
        树形化总过程:遍历桶中的元素,创建相同个数的树形节点,复制内容,建立起联系
然后让桶第一个元素指向新建的树头结点,替换桶的链表内容为树形内容
但是我们发现,之前的操作并没有设置红黑树的颜色值,现在得到的只能算是个二叉树。在 最后调用树形节点 hd.treeify(tab) 方法进行塑造红黑树。红黑树的构造就看我github不久后的复习笔记吧。
    */
    //如果冲突达到8位,就转树形结构,这就是转型的代码:
    //将桶内所有的 链表节点 替换成 红黑树节点
     final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //如果当前哈希表为空,或者哈希表中元素的个数小于 进行树形化的阈值(默认为 64),就去新建/扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
            //如果哈希表中的元素个数超过了 树形化阈值,进行树形化
             // e 是哈希表中指定位置桶里的链表节点,从第一个开始
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;//红黑树的头、尾节点
            do {
             //新建一个树形节点,内容和当前链表节点 e 一致
                TreeNode<K,V> p = replacementTreeNode(e, null);
                //确定树头节点
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
             //让桶的第一个元素指向新建的红黑树头结点,以后这个桶里的元素就是红黑树而不是链表了
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }
    /*
    扩容机制,也是确定容量的方法
    扩容(resize)就是重新计算容量,向HashMap对象里不停的添加元素,而HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。当然Java里的数组是无法自动扩容的,方法是使用一个新的数组代替已有的容量小的数组,就像我们用一个小桶装水,如果想装更多的水,就得换大水桶。
    */
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
         // 超过最大值就不再扩充了,就只好随意覆盖
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
             // 没超过最大值,就扩充为原来的2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 计算新的resize上限
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
         // 把每个bucket都移动到新的buckets中
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                             // 原索引
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else { // 原索引+oldCap
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {// 原索引放到bucket里
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) { // 原索引+oldCap放到bucket里
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
    /*
        删除:
        1.计算哈希值找到对应的桶
        2.在桶中寻找,当然查之前要判断桶类型是红黑树还是链表
        3.找到只会就删除嘛,当然也要对应桶类型
    */
    public V remove(Object key) {
        Node<K,V> e;
        //查找到则返回该结点,没有则返回null
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
             // 直接命中
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)// 如果是红黑树在红黑树中查找
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {// 在链表中查找
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            //终于找到了??那就去删除啊
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode) // 在红黑树中删除节点
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)// 链表首节点删除
                    tab[index] = node.next;
                else // 多节点单链表删除
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }
    /*
        清空:遍历所有桶的所有元素并至null
    */
    public void clear() {
        Node<K,V>[] tab;
        modCount++;
        if ((tab = table) != null && size > 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++i)
                tab[i] = null;
        }
    }

}

e.value = value;

jdk1.8的扩容

e.recordAccess;

使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果。

这里写图片描述

return oldValue;

元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:

这里写图片描述

}

在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”.

}

既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别,JDK1.7中rehash的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,但是从上图可以看出,JDK1.8不会倒置。

// 如果i索引处的Entry为null,表明此处还没有Entry。

对比jdk1.7:插入和扩容方法

modCount++;

说明:jdk1.7查询是的计算哈希,遍历单链表。因为它们怎么改结构,本质还是个哈希。而jdk1.8在冲突小于8的时候是像1.7的查询方式,但大于8的时候,就会改成红黑树,使用二叉查找树的结构性查询方式了,并且jdk1.8的插入涉及的存储结构的转换,从链地址法冲突处理到8位后就改成红黑树存储。

// 将key、value添加到i索引处。

来看下1.7的插入和扩容机制源码,简单得不行。

/*
    可以看到很简单的步骤:1.计算哈希,找到对应的Entry,;2.插入单链表到头部
*/
public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);//注意,HashMap可以存放null的key!!当然只能存一个!下面我们来看看,怎么放null的
        int hash = hash(key);
        int i = indexFor(hash, table.length);//计算哈希
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {//计算的哈希值锁定对应的Entry并且遍历单链表
            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;
    }
private V putForNullKey(V value) {
//nullkey的话,就锁定第一个Entry了,遍历单链表找到插入位置先
//如果找到了e.key==null,就保存null值对应的原值oldValue,然后覆盖原值,并返回oldValue
//如果在table[0]Entry链表中没有找到就调用addEntry方法添加一个key为null的Entry
        for (Entry<K,V> 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++;
        addEntry(0, null, value, 0);//添加
        return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
//判断是否要扩容.hashmap每次扩容的大小为2倍原容量,默认容量为16,hashmap的capacity会一直是2的整数幂。
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

//扩容
void resize(int newCapacity) {//传入新的容量
        Entry[] oldTable = table;//引用扩容前的Entry数组
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {//扩容前的数组大小如果已经达到最大(2^30)了
            threshold = Integer.MAX_VALUE; //这样的话就修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
            return;
        }

        Entry[] newTable = new Entry[newCapacity];//初始化一个新的Entry数组
        transfer(newTable, initHashSeedAsNeeded(newCapacity));//将数据转移到新的Entry数组里,并判断是否需要更新哈希值
        table = newTable;//HashMap的table属性引用新的Entry数组
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//修改阈值
    }
void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        //根据put中锁定的Entry去遍历
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {//要不要重新分配hash
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);//重新计算每个元素在数组中的位置,找到存放在新数组中的位置,再放置
                e.next = newTable[i];//标记
                newTable[i] = e; //将元素放在数组上
                e = next;//访问下一个Entry链上的元素
            }
        }
    }

addEntry(hash, key, value, i);

找了一张好图,说明JDK1.7的。原文

这里写图片描述

return null;

假设原来大小只是2,那么扩容根据2的次幂,就是到4了。然后重新计算分配hash,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。所有的Node重新rehash的过程。

}

三、再次总结关键点:

从源码得:当我们往HashMap中put元素时,先根据key的hashCode重新计算hash值,根据hash值得到这个元素在数组的位置,如果数组该位置已经存放了其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。

(1)实现了Map、Cloneable、java.io.Serializable接口。意味着支持全部map操作,支持被克隆,支持序列化,能通过序列化去传输。

addEntry(hash,key,value,i)方法根据计算出的hash值,将Key-Value对放在数组table的i索引处。addEntry是HashMap提供的一个包访问权限的方法,方法如下:

(2)HashMap的函数则是非同步的,它不是线程安全的。

void addEntry(int hash, K key, V value, int bucketIndex) {

若要在多线程中使用HashMap,需要我们额外的进行同步处理。 对HashMap的同步处理可以使用Collections类提供的synchronizedMap静态方法,或者直接使用JDK 5.0之后提供的java.util.concurrent包里的ConcurrentHashMap类。

// 获取指定 bucketIndex 索引处的 Entry

(3)HashMap的key、value都可以为null。

Entry<K,V> e = table[9159.com,bucketIndex];

HashMap的key、value都可以为null。 当HashMap的key为null时,HashMap会将其固定的插入table[0]位置(即HashMap散列表的第一个位置);而且table[0]处只会容纳一个key为null的值,当有多个key为null的值插入的时候,table[0]会保留最后插入的value。

// 将新创建的 Entry 放入 bucketIndex 索引处,并让新的 Entry 指向原来的 Entry

(4)HashMap只支持Iterator(迭代器)遍历。是“从前向后”的遍历数组;再对数组具体某一项对应的链表,从表头开始进行遍历。

table[bucketIndex] = new Entry<K,V>(hash, key, value, e);

方式是:1.通过entrySet()获取“Map.Entry集合”。2. 通过iterator()获取“Map.Entry集合”的迭代器,再进行遍历。

public class TestHashMap {
    public static void main(String[] args) {

        HashMap<String, String> hashMap = new HashMap<String, String>();
        for (int i = 0; i < 100000; i++) {
            hashMap.put(String.valueOf(i), "fuzhu");
        }

        Iterator it = hashMap.keySet().iterator();//遍历输出值。前提先拿到一个装载了key的Set集合
        long start = System.nanoTime();
        while(it.hasNext()) {
            String key = (String)it.next();
            //System.out.println("key:" + key);
            //System.out.println("value:" + hashMap.get(key));
        }
        long time = System.nanoTime() - start;

        long start2 = System.nanoTime();
        Iterator it2 = hashMap.entrySet().iterator();
        while(it2.hasNext()) {
            Map.Entry key = (java.util.Map.Entry)it2.next();
            //System.out.println("key:" + key);
          //  System.out.println("value:" + hashMap.get(key));
        }
        long time2 = System.nanoTime() - start2;
        System.out.println("测试耗时1!!!!"+time);
        System.out.println("---------------------------------");
        System.out.println("测试耗时2!!!!"+time2);
    }
}
/*
    最终结果:
    如果注释部分不执行,keySet方式是比entrySet快得多(对应下图1),但是注释部分执行时,也就是真正的遍历取值时,entrySet比keySet快得多(对应下图2)
*/
//原因:keySet方式拿到的是装载String的set(需要再次转换拿到key),而entrySet方式拿到的是装载Map.Entry类型的set,无须再次转换,直接getvalue

// 如果 Map 中的 key-value 对的数量超过了极限

图1

这里写图片描述

if (size++ >= threshold)

图2

这里写图片描述

// 把 table 对象的长度扩充到原来的2倍。

(5)HashMap的工作原理:

resize(2 * table.length);

通过hash的方法,通过put和get存储和获取对象。存储对象时,我们将K/V传给put方法时,它调用hashCode计算hash从而得到bucket桶位置,然后根据TREEIFY_THRESHOLD判断桶装载的类型,红黑树还是链表,再进一步存储,HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时,我们将K传给get,它调用hashCode计算hash从而得到bucket位置,然后根据TREEIFY_THRESHOLD判断桶装载的类型,并进一步调用equals()方法确定键值对。

}

在Java 8中,如果一个bucket桶中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。

当系统决定存储HashMap中的Key-Value对时,完全没有考虑Entry中的Value,仅仅只是根据key来计算并决定每个Entry的存储位置。即当系统决定了key的存储位置之后,value随之保存在那里即可。

(6)equals()和hashCode()的都有什么作用?

hash方法根据key的hashCode重新计算一次散列。此算法加入了高位计算,防止低位不变,高位变化时,造成的hash冲突。

通过对key的hashCode()进行hashing,并计算下标( n-1 & hash),从而获得buckets的位置。如果产生碰撞,则利用key.equals()方法去链表或树中去查找对应的节点

static int hash {

因为hashcode相同,所以它们的bucket位置相同,‘碰撞冲突’会发生。因为HashMap使用链表或红黑树存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表或红黑树中。

h ^= (h >>> 20) ^ (h >>> 12);

找到bucket桶位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象。因此,设计HashMap的key类型时,如果使用不可变的、声明作final的对象,并且采用合适的equals()和hashCode()方法的话,将会减少碰撞的发生,提高效率。

return h ^ (h >>> 7) ^ (h >>> 4);

(7)HashMap添加元素时,是使用自定义的哈希算法。HashMap不支持contains(Object value)方法,没有重写toString()方法。

}

(8)HashMap的大小超过了负载因子(load factor)定义的容量,会怎样?

我们得知在HashMap中要找到某个元素,需要根据key得到hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。上面说过HashMap的数据结构是数组和链表的结合,所以我们当然希望这个HashMap中的元素位置尽量的分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,而不用再去遍历链表,这样就大大的优化了查询的效率。

超过了负载因子(默认0.75),则会重新resize一个原来长度两倍的HashMap,并且重新调用hash方法。默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,jdk1.7会重新计算哈希值,但是jdk1.8很少重新计算,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。

对于任意给定的对象,只要它的HashCode()返回值相同,那么程序调用Hash方法所计算得到的hash值总是相同的。我们首先想到的就是把Hash值对数组的长度取模运算,这么一来,元素的分布相对来说是比较均匀的。但是模运算的消耗还是比较大的,HashMap中:调用indexFor(int h,int length)方法来计算该对象应该保存在table数组的哪个索引处。

(9)重新调整HashMap大小出现的线程问题:

static int indexFor(int h, int length) {

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

return h & ;

(10)为什么String, Interger这样的wrapper类适合作为键?

}

因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能

HashMap底层数组的长度总是2的n次方,这是HashMap在速度上的优化。

参考:此博主此文章

当数组长度为2的n次幂的时候,不同的Key算得的index相同的几率较小,那么数据在数组上分布就比较均匀,也就是碰撞的几率·比较小。相对的,查询的时候就不用遍历某个位置上的链表,这样查询的效率也就比较高了。

(11)使用的取舍:

4.HashMap的读取实现:

1. 若在单线程中,我们往往会选择HashMap;而在多线程中,则会选择Hashtable。

public V get(Object key) {

2.若不能插入null元素,则选择Hashtable;否则,可以选择HashMap。

if (key == null)

3.在多线程中,我们可以自己对HashMap进行同步,也可以选择ConcurrentHashMap。当HashMap和Hashtable都不能满足自己的需求时,还可以考虑新定义一个类,继承或重新实现散列表;当然,一般情况下是不需要的了。


return getForNullKey();

好了,深入Java基础(四)--哈希表(1)HashMap应用及源码详解讲完了。本博客系列是这个系列的第五篇,阅读这些源码收获很大,当然过程也是很有点苦逼的,比如这篇我之前不小心没保存,前前后后4天才写完,当然也不后悔,这是积累的必经一步,我会继续出这个系列文章,分享经验给大家。欢迎在下面指出错误,共同学习!!你的点赞是对我最好的支持!!

int hash = hash(key.hashCode;

更多内容,可以访问JackFrost的博客

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.equals

return e.value;

}

return null;

}

从HashMap中get元素时,首先计算key的hashCode,找到数组中对应位置的某一个元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。即:HashMap在底层将key-Value当成一个整体进行处理,这个整体就是一个Entry对象。HashMap底层采用了一个Entry[]数组来保存所有的键值对,当需要存储一个Entry对象时,会根据hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry时,也会根据hash算法找到其在数组中的存储位置,在根据equals方法从该位置上的链表中取出该Entry。

5.HashMap的resize:

当hashMap中的元素越来越多的时候,hash冲突的几率也越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对HashMap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,这是一个常用的操作,而在HashMap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。当HashMap中的元素个数超过数组大小loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为16,那么当HashMap中元素个数超过16*0.75=12的时候,就把数组的大小扩容为2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。

6.Fail-Fast机制:

我们知道HashMap不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了Map,那么将抛出ConcurrentModificationException,这就是所谓fail-fast策略。这一策略在源码中的实现是用过modCount域对HashMap内容的修改都将增加这个值,那么在迭代器初始化过程中会将这个值赋给迭代器的expectModCount。在迭代过程中,判断modCount跟expectModCount是否相等,如果不想等就表示已经有其他线程修改了Map。(modCount声明为volatile,保证了线程之间的可见性)。

final Entry<K,V> nextEntry() {

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

7.关于HashMap的问题:

为什么String、Integer这样的wrapper类适合作为键?

String、Integer这样的wrapper类作为HashMap的键是在适合不过了,而且String最为常用,因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算HashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashCode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashCode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。

我们可以使用自定义的对象作为键吗?

这是前一个问题的延伸。当然你可能使用任何对象作为键,只要它遵循了equals()和hashCode()方法的定义规则,并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的,那么它已经满足了作为键的条件,因为当它创建之后就已经不能改变了。

我们可以使用ConcurrentHashMap来代替HashTable吗?

这是另外一个很热门的面试题,因为ConcurrentHashMap越来越多人用了。我们知道HashTable是synchronized的,但是ConcurrentHashMap同步性能更好,因为它仅仅根据同步级别对Map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable,但是HashTable提供更强的线程安全性。

二、HashTable

1.HashTable概述:

和HashMap一样,HashTable也是一个散列表,它存储的内容是键值对映射。HashTable继承于Dictionary,实现了Map、Cloneable、java.io.Serializable接口。HashTable的函数都是同步的,这意味着它是线程安全的。它的Key、Value都不可以为null。此外,HashTable中的映射不是有序的。

HashTable的实例有两个参数影响其性能:初始容量和加载因子。容量是哈希表中桶的数量,初始容量就是哈希表创建时的容量。注意,哈希表的状态为open:在发生“哈希冲突”的情况下,单个桶会存储多个条目,这些条目必须按顺序搜索。加载因子是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。关于何时以及是否调用rehash方法的具体细节则依赖于该实现。通常,默认加载因子是0.75。

2.Hash Table的数据结构:

HashTable与Map关系如下

public class Hashtable<K,V>

extends Dictionary<K,V>

implements Map<K,V>, Cloneable, java.io.Serializable

HashTable并没有去继承AbstractMap,而是选择继承了Dictionary类,Dictionary是个被废弃的抽象类。

3.实现原理:

成员变量跟HashMap基本类似,但是HashMap更加规范,HashMap内部还定义了一些常量,比如默认的负载因子,默认的容量,最大容量等。

public Hashtable(int initialCapacity, float loadFactor) {//可指定初始容量和加载因子

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal Capacity: "+

initialCapacity);

if (loadFactor <= 0 || Float.isNaN(loadFactor))

throw new IllegalArgumentException("Illegal Load: "+loadFactor);

if (initialCapacity==0)

initialCapacity = 1;//初始容量最小值为1

this.loadFactor = loadFactor;

table = new Entry[initialCapacity];//创建桶数组

threshold = Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);//初始化容量阈值

useAltHashing = sun.misc.VM.isBooted() &&

(initialCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);

}

/**

* Constructs a new, empty hashtable with the specified initial capacity

* and default load factor .

*/

public Hashtable(int initialCapacity) {

this(initialCapacity, 0.75f);//默认负载因子为0.75

}

public Hashtable() {

this(11, 0.75f);//默认容量为11,负载因子为0.75

}

/**

* Constructs a new hashtable with the same mappings as the given

* Map. The hashtable is created with an initial capacity sufficient to

* hold the mappings in the given Map and a default load factor .

*/

public Hashtable(Map<? extends K, ? extends V> t) {

this(Math.max(2*t.size, 0.75f);

putAll;

}

——HashTable的默认容量为11,默认负载因子为0.75。(HashMap默认容量是16,默认负载因子也是0.75)

——HashTable的容量可以为任意整数,最小值为1,而HashMap的容量始终为2的n次方。

——为避免扩容带来的性能问题,建议指定合理容量。跟HashMap一样,HashTable内部也有一个静态类叫Entry,其实是个键值对,保存了键和值的引用。也可以理解为一个单链表的节点,因为其持有下一个Entry对象的引用。

4.HashTable的存取实现:

HashTable和HashMap存储的都是键值对对象,而不是单独的键或值。

public synchronized V put(K key, V value) {//向哈希表中添加键值对

// Make sure the value is not null

if (value == null) {//确保值不能为空

throw new NullPointerException();

}

// Makes sure the key is not already in the hashtable.

Entry tab[] = table;

int hash = hash;//根据键生成hash值---->若key为null,此方法会抛异常

int index = (hash & 0x7FFFFFFF) % tab.length;//通过hash值找到其存储位置

for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {/遍历链表

if ((e.hash == hash) && e.key.equals {//若键相同,则新值覆盖旧值

V old = e.value;

e.value = value;

return old;

}

}

modCount++;

if (count >= threshold) {//当前容量超过阈值。需要扩容

// Rehash the table if the threshold is exceeded

rehash();//重新构建桶数组,并对数组中所有键值对重哈希,耗时!

tab = table;

hash = hash;

index = (hash & 0x7FFFFFFF) % tab.length;//这里是取摸运算

}

// Creates the new entry.

Entry<K,V> e = tab[index];

//将新结点插到链表首部

tab[index] = new Entry<>(hash, key, value, e);//生成一个新结点

count++;

return null;

}

public synchronized V get(Object key) {//根据键取出对应索引

Entry tab[] = table;

int hash = hash;//先根据key计算hash值

int index = (hash & 0x7FFFFFFF) % tab.length;//再根据hash值找到索引

for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {//遍历entry链

if ((e.hash == hash) && e.key.equals {//若找到该键

return e.value;//返回对应的值

}

}

return null;//否则返回null

}

——HashTable并不允许值和键为空,若为空,则抛出空指针异常。

——HashMap计算索引的方式是h&,而HashTable用的是模运算,效率上是低于HashMap的。

——HashTable计算索引时将hash值先与上0x7fffffff,这是为了保证hash值始终为整数。

——HashTable中若干方法都添加了synchronized关键字,也就意味着这个HashTable是个线程安全的类,这是它与HashMap最大的不同点。

——HashTable每次扩容都是旧容量的2倍加2,而HashMap为旧容量的2倍。

本文由9159.com发布于编程,转载请注明出处:HashMap底层就是一个数组结构,HashMap中key与value都

关键词:

上一篇:没有了
下一篇:没有了