Java中的Map


Map

哈希表/散列表

通俗的说就是,使用散列函数将key值映射到数组下标,这样就可以根据key值直接访问到元素存储位置,这种结构就叫哈希表(散列表)。

将key值映射到数组下标的函数就做散列函数,这个映射过程是一个key值压缩的过程,因而不可避免会存在两个不同的值映射到了相同的下标的情况,这种情况叫做哈希冲突

散列函数的选取也是有套路可循的,比如除数取余法,平方取中法,数字分析法,折叠法扥等。

解决哈希冲突一般有两种方法:

  • 开放定址法

    如果遇到冲突,则向后几步再存;

  • 链接法(拉链法)

    如果遇到冲突,则在对应位置后面添加一个链表节点。

HashMap

允许key和value为null。

使用一个链表数组(bucket,也叫哈希表,散列表)来存储数据。

线程安全的。

查询的效率可以达到O(1)。

Java8中大部分情况是基于哈希表实现,当链表长度达到8的时候,转为红黑树实现。

不保证存取顺序;

具体的看存储结构:

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

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

        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;
        }
    }

看看树节点:

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;    
}

HashTable

不允许key和value为null。

使用一个链表数组(bucket,也叫哈希表,散列表)来存储数据。

线程不安全的。

先来看看查找的关键代码:

public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        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 (V)e.value;
            }
        }
        return null;
    }

可以看到,就是先取key的hash值,然后对表长取余确定好数组下标。然后从数组下标处的链表开始查找。

再来看看put操作的代码:

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 = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

private void addEntry(int hash, K key, V value, int index) {
        modCount++;

        Entry<?,?> tab[] = table;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
    }

还是通过对key做hash运算,然后取余得到数组下标,再进行遍历,如果已经存在对应的key,则替换新值;如果是新key,则添加到链表最前面。

并且可以看到value不可以为null,否则抛出异常。key也不能为null,要不然也会抛出空指针异常。

可以看到看到get/put方法都是同步的,保证了线程安全。

LinkedHashMap

双向链表与HashMap的结合。

保证插入的顺序,遍历的时候先得到的是先插入的元素。


文章作者: 姜康
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 姜康 !
评论
 上一篇
Java中的Lock Java中的Lock
Java 中保证线程安全,操作同步的方法有很多种,比如: 使用synchronized关键字 使用Lock的实现类 其中synchronized属于语言级别的处理,无需我们去处理细节,而Lock则是一个接口,我们可以自定义Lock或者使
2020-05-15
下一篇 
Java中的List Java中的List
List ArrayList通过动态数组存储数据的,数组默认长度为10,实际使用过程中可以通过trimToSize()方法剪裁到实际的list大小。 ArrayList是线程不安全的; ArrayList由于通过数组索引定位,所以查找效率比
2020-05-15
  目录