欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

源码剖析——HashMap、HashTable、HashSet的区别

程序员文章站 2022-05-06 07:53:33
...

1、HashMapHashTable 实际上是数组和链表的结合
源码剖析——HashMap、HashTable、HashSet的区别
2、HashMapHashTable 不允许添加相同key,若添加了已经存在的key,则会以最新的替代原来的,并返回上次的value
3、HashMap允许添加keyvaluenullHashTable不允许添加keyvaluenull
4、HashMap线程不安全,性能高,HashTable线程安全,方法中加synchronized关键字,性能较差
5、HashSet内部是基于HashMap实现的,也就是hashMapkey形成了HashSet,value

    private static final Object PRESENT = new Object();

HashMap元素key相同的话,不会另外添加到HashMap中,而是更新相同的keyvalue,这就保证了Hashset不能存储相同的数据。

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

6、内存扩容时采取的方式也不同,Hashtable采用的是2*old+1,而HashMap2*oldHashSet2*old
源码剖析——HashMap、HashTable、HashSet的区别
源码剖析——HashMap、HashTable、HashSet的区别
7、剖析CRUD:

HashMap&&HashTable

Create(增加):

    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        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++;
        addEntry(hash, key, value, i);
        return null;
    }
    private V putForNullKey(V value) {
        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) {
        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 createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

思路:1、首先通过key计算hash值 然后得到在table[]中的位置
2、然后根据put顺序,新增的放在链头,最先的放在链尾,从而形成hashmap结构为横向为数组table[],然后纵向为相同keyhash值的Entry<K,V>链表的形式。

Retrieve(查询):

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }
    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        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;
    }

思路:1、首先清楚结构是横向数组+纵向链表,首先利用key算出hash得到在数组中的索引值
2、得到索引值,然后e = e.next遍历链表,key相等则返回value
思考:首先初始化一个hashMap然后先添加数据,直到table.length发生改变,那么再get,那么indexFor(hash, table.length)的值不是和table.length 没发生改变前不一样吗,那么还能取出正确的数据吗?
多虑了,首先hashMap每次put,当里面的存储的数据大于table的容量的时候,就会自动将table的扩大2倍,看如下源码

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        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);
    }

在扩容的时候会重新生成一个空的数组,然后将老的数组中的数组重新按照新的table生成hash值,这样hashMap中数据的次序也会发生改变,但是这样就会保证putgethash都是同步的。

    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

Update(修改): (无)

Delete(删除):

    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }
   final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
        int hash = (key == null) ? 0 : hash(key);
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;

        while (e != null) {
            Entry<K,V> 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;
    }

思路:先找到然后和链表remove方法差不多,修改prev、next

看一下:HashMap、HashTable、HashSet都实现了java.io.Serializable这个序列化的接口,并且里面存储数据的数组都用transient关键字,然后利用writeObjectreadObject两个方法来实现序列化操作时写入、读出。
源码剖析——HashMap、HashTable、HashSet的区别