Java
18 分钟 读完 (大约 2736 个字) 0次访问

Hashtable、HashMap、TreeMap

Hashtable、HashMap、TreeMap都是比较常见的一些Map实现，它们都是key-value键值对的形式存储和操作数据的容器类，同时他们的元素中不能有重复的key,一个key也只能映射一个value值。

下面我从不同的维度来分别说说这三个集合，文章中涉及到的源码版本是JDK8

底层数据结构

  • Hashtable和HashMap底层都是采用数组存储数据
  • TreeMap底层是采用红黑树存储数据

元素特性

Hashtable

Hashtable中存储的key和value都不能为null，这个从它的源码实现是可以看出来的

1
2
3
4
5
6
7
8
9
10
11
12
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();
    ...//省略部分
    return null;
}

这是Hashtable添加元素的源码实现，从开头的if判断就可以发现它的value值是不允许为null的，而它的key虽然没有显式判断，但是在执行int hash = key.hashCode();这句代码时，如果key为null的话，代码执行到这里程序就崩了，所以从侧面也反应出key也不能为null

HashMap

HashMap中存储的key和value都允许为null，这个依然是从源码中看出来的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//HashMap的put方法具体实现比较复杂代码比较多，这里我只贴出添加元素时涉及到key和value的相关代码
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
    return new TreeNode<>(hash, key, value, next);
}

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

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

//TreeNode最终还是继承自Node，所以这里就不贴出TreeNode的构造函数了

从上面的几段代码中可以看到在将key-value添加到HashMap中时没有任何地方会使用它们，因此key和value都是可以为null的

但是一个HashMap中只能有一个key为null，但是可以有多个value为null

TreeMap

TreeMap中如果用户未实现Comparator接口，则key不能为null，如果实现了Comparator接口，那么key能否为null则需要根据Comparator接口的具体实现有关。value则是可以为null。至于原因，我们依然通过源码来寻求答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public V put(K key, V value) {
    ...
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    } else {
        if (key == null)
            throw new NullPointerException();
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    ...
    return null;
}

通过上面的代码可以很明显的看到当成员变量comparator为空时(Comparator接口未实现)，有明显的key的非空判断，而当实现了该接口后，这会通过Comparator接口的compare方法比较当前key与TreeMap中已存在的key是否相等，所以这个时候key能否为nul就跟Comparator接口的compare方法具体实现有关了。

注意这段代码

1
2
3
4
5
6
7
cmp = k.compareTo(t.key);
if (cmp < 0)
    t = t.left;
else if (cmp > 0)
    t = t.right;
else
    return t.setValue(value);

从上面的代码中我们还可以看出TreeMap的key是有序的，而且当前节点的key比其左子树节点的key要大，而比右子树节点的key要小。

有序性

  • Hashtable和HashMap都是无序的
  • TreeMap的key是有序的，有序的原因在前面分析其put源码的时候已经说过了。要注意的是这里是key是有序的，而不是其value是有序的，而且其默认是升序排序方式(深度优先搜索)，对于其排序方式，可以自定义实现Comparator接口来自定义排序规则

初始化和扩容方式

Hashtable

  1. 默认初始化容量为11个
  2. 容量阈值默认为当前容量的0.75倍，当集合数据大于等于阈值时就会进行扩容
  3. 不要求底层数组的容量一定为2的幂次方
  4. 扩容时会将容量变为原来的2倍加1
  5. 在初始化时就会创建底层数组
  6. 扩容时会创建一个扩容后的新数组，然后将原来数组的数据拷贝到新数组中
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    private void addEntry(int hash, K key, V value, int index) {
        ...
        if (count >= threshold) {//数据个数大于等于阈值时进行扩容
            rehash();
            ...
        }
        ...
    }
    //扩容函数
    protected void rehash() {
        int oldCapacity = table.length;
        Entry<?,?>[] oldMap = table;
        
        //此处将oldCapacity左移一位，即将其扩大一倍
        int newCapacity = (oldCapacity << 1) + 1;
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

        modCount++;
        //重新计算容量阈值
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        table = newMap;
        //拷贝数据
        for (int i = oldCapacity ; i-- > 0 ;) {
            for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                Entry<K,V> e = old;
                old = old.next;

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = (Entry<K,V>)newMap[index];
                newMap[index] = e;
            }
        }
    }

HashMap

  1. 默认初始化容量为16个
  2. 容量阈值默认为当前容量的0.75倍，当集合数据大于等于阈值时就会进行扩容
  3. 底层数据的容量要求一定是2的幂次方
  4. 扩容时会将容量变为原来的2倍
  5. 初始化时不会创建底层数组，而是在调用put方法添加数据时再创建底层数据
  6. 扩容时会创建一个扩容后的新数组，然后将原来数组的数据拷贝到新数组中
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;//初始化创建底层数组
        ...
        if (++size > threshold)//元素个数大于等于阈值则进行扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }
    //初始化或扩容函数
    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) {//MAXIMUM_CAPACITY=2^30
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)//此处的newCap = oldCap << 1则是进行数组扩容一倍
                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);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);//重新计算新的阈值
        }
        threshold = newThr;
        ....
        return newTab;
    }

TreeMap

  1. 因为TreeMap是树结构，所以不存在容量和扩容的问题
  2. 初始化时不会创建其根节点，而是在调用put方法添加数据时才会创建其根节点

线程安全性

Hashtable

其方法都采用了synchronized修饰，因此是线程安全的，不会出现两个线程同时对数据进行操作的情况，它保证了线程安全性。但也因为这样导致其在多线程环境下使用此集合效率低下，因为一个线程访问其同步方法时，其他访问Hashtable的线程都会处于阻塞状态，现在已不推荐使用此集合。

HashMap

HashMap的方法没有采用synchronized修饰，所以是非线程安全的，在程序中任一时刻可能会存在多个线程同时修改其数据，从而导致数据不一致。

在多线程环境下，我们可以使用下面两种方式使用HashMap

  1. 使用Collections.synchronizedMap()方法将HashMap转换为线程安全的SynchronizedMap包装类,其内部也是使用synchronized来达到同步效果，只不过此时锁住的是一个Object类型的成员变量,和锁住HashMap对象本身效果是一样，效率也比较低下，仅仅适合用在并发度不高的情景。
  2. 使用ConcurrentHashMap集合，相较于Hashtable锁住的是对象整体， ConcurrentHashMap基于lock实现锁分段技术。首先将Map存放的数据分成一段一段的存储方式，然后给每一段数据分配一把锁，当一个线程占用锁访问其中一个段的数据时，其他段的数据也能被其他线程访问。ConcurrentHashMap不仅保证了多线程运行环境下的数据访问安全性，而且性能上有长足的提升

TreeMap

HashMap的方法没有采用synchronized修饰，所以TreeMap也是非线程安全的。

在多线程环境下建议使用ConcurrentSkipListMap代替

HashMap的哈希冲突

HashMap采用链地址法来解决哈希冲突，对哈希冲突或链地址法不了解的同学请参考我的另外一篇文章Hash冲突解决方法

但是在HashMap中对链地址法采用了一点点变化，对于哈希冲突导致出现同义词元素显示采用单链表存放，当这个链表大小超过一个阈值(TREEIFY_THRESHOLD=8)且HashMap的大小大于等于另一个容量阈值(MIN_TREEIFY_CAPACITY = 64),就会把这个单链表该造为树形结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            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;
                }
                ...
            }
        }
        ...
    }
   ...
    return null;
}

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        //HashMap的元素大小大于等于MIN_TREEIFY_CAPACITY则将该单链表改造成红黑树
        //树改造逻辑
    }
}

为什么要改造呢，我的理解是这样的：

  • 因为单链表适合数据的插入和删除，而对于查询来说其效率要低一点，在单链表数据量小的时候，查询遍历的效率可能影响不太大，而当单链表数据量变大之后，其查询带来的性能影响就没法忽略了，所以这里就对单链表改造为红黑树，这样其key是有序的，查询的时候性能就要提高很多。
  • 还有一种说法是因为安全性。因为构造哈希冲突的数据难度不大，会有人利用恶意代码产生大量这种数据与服务器交互，导致服务器CPU资源被大量占用，这样就会导致哈希碰撞拒绝服务器攻击。

原创文章，转载请出处注明。

下面是我的个人公众号，欢迎关注交流

# Java

喜欢这篇文章？打赏一下作者吧

整洁代码的理解
Hash冲突解决方法
关注我

分类

链接

标签云

Android AndroidStudio Behavior Coroutine DB Flutter Hexo IM JSONP Java JavaScript Kotlin Linux Material Design Media OkHttp RN RecyclerView Retrofit Room RxJava Shape SpannableStringBuilder Thinking View WordPress 多线程 小程序 百度地图 译

最新文章

归档

标签

Android 38
AndroidStudio 1
Behavior 3
Coroutine 3
DB 1
Flutter 4
Hexo 1
IM 5
JSONP 1
Java 11
JavaScript 1
Kotlin 3
Linux 5
Material Design 3
Media 1
OkHttp 2
RN 1
RecyclerView 4
Retrofit 3
Room 1
RxJava 1
Shape 1
SpannableStringBuilder 1
Thinking 1
View 2
WordPress 2
多线程 4
小程序 3
百度地图 1
译 1

最新文章

归档

标签

Android 38
AndroidStudio 1
Behavior 3
Coroutine 3
DB 1
Flutter 4
Hexo 1
IM 5
JSONP 1
Java 11
JavaScript 1
Kotlin 3
Linux 5
Material Design 3
Media 1
OkHttp 2
RN 1
RecyclerView 4
Retrofit 3
Room 1
RxJava 1
Shape 1
SpannableStringBuilder 1
Thinking 1
View 2
WordPress 2
多线程 4
小程序 3
百度地图 1
译 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×