文章目录
  1. 1. 两者区别
  2. 2. HashMap实现
    1. 2.1. put
    2. 2.2. get
    3. 2.3. null key的存取
  3. 3. 解决hash冲突的办法
  4. 4. HashTable如何实现线程安全
  5. 5. ConcurrentHashMap
  6. 6. 参考

一看到这个题目,目测很多小伙伴都会想到某次面试的场景,这的确是一道特别常见的Java面试题。除了介绍一下两者的区别之外,我希望今天可以更进一步了解两者。

两者区别

  1. Hashtable是基于陈旧的Dictionary类的,HashMap是Java 1.2引进的Map接口的一个实现。
  2. 最重要的不同是Hashtable的方法是同步的,而HashMap的方法不是。
  3. HashMap可以将空值作为一个表的条目的key或value。

HashMap实现

HashMap实际上是一个“链表的数组”的数据结构,每个元素存放链表头结点的数组,即数组和链表的结合体。

HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。

transient Entry[] table;

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

put

疑问:如果两个key通过hash%Entry[].length得到的index相同,会不会有覆盖的危险?

这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。打个比方, 第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A。一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。

public V put(K key, V value) {
    // HashMap允许存放null键和null值。
    // 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。
    if (key == null)
        return putForNullKey(value);
    // 根据key的hashCode重新计算hash值。
    int hash = hash(key.hashCode());
    // 搜索指定hash值所对应table中的索引。
    int i = indexFor(hash, table.length);
    // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。
    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;
        }
    }
    // 如果i索引处的Entry为null,表明此处还没有Entry。
    // modCount记录HashMap中修改结构的次数
    modCount++;
    // 将key、value添加到i索引处。
    addEntry(hash, key, value, i);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 获取指定 bucketIndex 索引处的 Entry 
    Entry<K,V> e = table[bucketIndex];
    // 将新创建的 Entry 放入 bucketIndex 索引处,并让新的 Entry 指向原来的 Entry
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    // 如果 Map 中的 key-value 对的数量超过了极限
    if (size++ >= threshold)
    // 把 table 对象的长度扩充到原来的2倍。
        resize(2 * table.length);
}

get

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    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(k)))
            return e.value;
    }
    return null;
}    

null key的存取

null key总是存放在Entry[]数组的第一个元素。

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

private V getForNullKey() {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

解决hash冲突的办法

  1. 开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列)

    当关键字key的hash地址p冲突时,以p为基础,直到产生另一个hash地址。

  2. 再哈希法

    使用多个hash函数

  3. 链地址法

    使用链表

  4. 建立一个公共溢出区

    hash表分为基本表和溢出表,凡是和基本表发生冲突的元素,一律填入溢出表。

Java中hashmap的解决办法就是采用的链地址法。

HashTable如何实现线程安全

实现方法和hashMap一样,不过通过synchronized关键字来实现线程安全。

但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法时,其他线程访问HashTable的同步方法时,可能会进入阻塞或轮询状态。如线程1使用put进行添加元素,线程2不但不能使用put方法添加元素,并且也不能使用get方法来获取元素,所以竞争越激烈效率越低。

ConcurrentHashMap

HashTable容器在竞争激烈的并发环境下表现出效率低下的原因是所有访问HashTable的线程都必须竞争同一把锁,那假如容器里有多把锁,每一把锁用于锁容器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效的提高并发访问效率,这就是ConcurrentHashMap所使用的锁分段技术,首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。

参考

  1. HashMap实现原理分析
  2. 聊聊并发(四)——深入分析ConcurrentHashMap
文章目录
  1. 1. 两者区别
  2. 2. HashMap实现
    1. 2.1. put
    2. 2.2. get
    3. 2.3. null key的存取
  3. 3. 解决hash冲突的办法
  4. 4. HashTable如何实现线程安全
  5. 5. ConcurrentHashMap
  6. 6. 参考