Java第2篇: 哈希表

Java提供了一种很重要的结构HashMap。在将HashMap之前，先讲讲哈希表这种结构。

哈希表

HashMap其实就是一种哈希表结构。在哈希表这种结构中，数据是以key-value的形式进行存储的，主要有put和get这两种基本操作，put操作将数据以key-value的形式插入到哈希表，get操作根据key查询对应的value。

 

在向哈希表结构中插入数据时，以key-value的形式，根据key计算一个hash值，这个哈希值决定该数据存放哪个bucket。

 

除了HashMap，Java还提供了多种哈希表的实现，Java中比较常见的Hash实现有HashMap，Hashtable，ConcurrentHashMap。

 

这种结构在Java中也有很多地方使用到。

 

 

Hash通常是无序的。Java中也提供了一种有序的TreeMap。

HashMap (java.util.HashMap)是Map接口最基本的一个哈希表实现，它不是线程安全的，同时允许key为null。HashMap中的元素是无序的，也不保证顺序。在没有触发扩容的扩容的情况下，HashMap的基本操作如get和put性能稳定，也就是在时间复杂度上是稳定的。同时，有两个影响HashMap性能的参数：初始容量和加载因子。

 

负载因子

哈希表的负载因子定义为：α=填入表中的元素个数 / 哈希表的长度。α是散列表装满程度的标志因子。

 

默认负载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

也就是如果哈希中元素的个数达到（大于或等于）某个阈值，就触发扩容，这个阈值的计算为哈希表的长度*负载因子。

 

容量设置

HashMap容量设置为一个2的n次方的数, 即power-of-two，如1,2,4,8,16,32,64,128 ...，在构造HashMap时，如果指定了初始容量，如通过public HashMap(int initialCapacity, float loadFactor)构造函数进行构造，这里第一个参数指定初始容量，但并不是简单的将HashMap容量设置为该参数值，而是像这样的：

 

// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
  capacity <<= 1;

 

它实际上指定的是一个2的N次方的一个值，且这个值刚刚大于（不小于）指定的初始容量。从这里可以看出，HashMap的容量一定是一个2的N次方的一个值，且最大为1 << 30。

 

有没有奇怪HashMap的容量为什么要设置为2的幂这样的值？Hashtable就不是这样。而ConcurrentHashMap的内部实现也和HashMap一样为2的幂这样的值？

 

最大容量

HashMap最大容量为1 << 30，也就是2的30次方。

 

static final int MAXIMUM_CAPACITY = 1 << 30;

 

 

 

The maximum capacity, used if a higher value is implicitly specified
by either of the constructors with arguments.
MUST be a power of two <= 1<<30.

 

 

 

这个是HashMap中桶的最大容量，但并不是最大可put的元素的最大数量。最大可put的元素的数量为int的最大值，即2的31次方－1。

 

 

默认容量

默认情况下，如果没有指定初始容量，默认初始化容量为16。

 

static final int DEFAULT_INITIAL_CAPACITY = 16;

哈希函数

Java中哈希函数挺不好理解的，因为Java 中的哈希表结构所使用的hash函数都依赖于一个hashCode方法，而该方法是从基类Object继承过来的，且由jvm实现。另外在子类可以重写hashCode方法， jdk提供的很多类都重写了该方法，尽管都实现的很简单，但也给java中的哈希表结构的哈希函数很大的灵活性和理解的困难。即便是java中最简单的哈希表实现HashMap，要理解它的哈希函数也是很困难。

 

 

 

HashMap的哈希函数

HashMap在对key计算哈希以决定将数据存在哪个bucket中涉及到3个哈希函数。

 

它首先通过hashCode方法计算key的hashCode

 

public native int hashCode();

 然后对hashCode再次计算了一次hash，如下：

 

 

static int hash(int h) {
  // This function ensures that hashCodes that differ only by
  // constant multiples at each bit position have a bounded
  // number of collisions (approximately 8 at default load factor).
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}

 

这是第2次哈希计算，由于HashMap使用power-of-two的容量大小，才有这步，如果不是使用power-of-two的容量大小，就不需要这步了，这样也就是跟HashTable一样的计算哈希了。

 

这次的hash计算用于确保在各个bit上发生碰撞的次数是有限的，没具体研究。

 

Java 8的第2次哈希计算：

 

h ^ (h >>> 16)

 

源代码如下：

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

 

 

 

最后在根据第2次哈希计算的结果调用indexFor方法计算出最终的一个哈希值，它最终确定数据存在哪个bucket：

 

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

 这步很简答，indexFor方法如下：

static int indexFor(int h, int length) {
  return h & (length-1);
}

 

由于HashMap桶的容量取的是大于指定容量capacity的第一个2的n次方的值，所以h & (length-1)和m%length结果一样，但这种位运算的写法比模余的写法效率更高。

 

 

这段代码是什么意思？

if (oldCapacity == MAXIMUM_CAPACITY) {
  threshold = Integer.MAX_VALUE;
  return;
}

 

 

在进行扩容时，如果当前容量已经达到最大容量，这将threshold值设置为为int的最大值，即2的31次方－1，并不再进行扩容，也就不需要再重新计算哈希。从这里可以看出：HashMap最大容量为1 << 30，也就是2的30次方；最大可put的元素的数量为int的最大值，即2的31次方－1。

 

关于HashMap最大可放多少个的问题（即最大可put的元素的个数）

之前是认为最大可放int的最大值，即2的31次方－1个。

我觉得理论上是无限的。

 

 

 

 

HashMap构造

public HashMap()

 

 

Constructs an empty <tt>HashMap</tt> with the default initial capacity (16) and the default load factor (0.75).

 

public HashMap(int initialCapacity)

 

Constructs an empty <tt>HashMap</tt> with the specified initial capacity and the default load factor (0.75).

 

public HashMap(int initialCapacity, float loadFactor)

 

Constructs an empty <tt>HashMap</tt> with the specified initial capacity and load factor.

 

public HashMap(Map<? extends K, ? extends V> m)

 

 

Constructs a new <tt>HashMap</tt> with the same mappings as the specified <tt>Map</tt>. The <tt>HashMap</tt> is created with default load factor (0.75) and an initial capacity sufficient to hold the mappings in the specified <tt>Map</tt>.

 

 

HashMap允许key为null，当key为null时，数据存在第一个bucket，也就是下标为0的bucket。

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

 

 

 

 

 

Threshold设置

 

threshold = (int)(capacity * loadFactor);

 

 

关键字比较

 

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

 

扩容

当Map中的元素数目达到或超过threshold值时，将自动扩容，扩容后的容量是之前的两倍。

resize(2 * table.length)

 上面提得到HashMap的容量设置为2的n次方的一个数，扩容后新的容量为当前容量的2倍，也就是2的n+1次方。

 

重新计算哈希

在进行扩容时，需要重新计算哈希。

 

关键代码

 

 

HashMap实现的好吗?

HashMap实现的很好，但还不是很好。除了初始容量和加载因子这两个影响HashMap性能的参数，它还依赖于key的hashCode算法。同时，在计算哈希时计算了两次哈希。

 

Segment

Java并发编程包中提供的支持并发编程环境下的Map实现ConcurrentHashMap，并发编程通常是在多线程的环境下，需要保证类是线程安全的，ConcurrentHashMap通过Segment来分段，Segment继承了ReentrantLock类，因此支持加锁同步，通过这种方式来保证线程安全。同时通过这种分段的方式，减少每次操作map时都需要执行同步操作而必须阻塞从而无法继续执行的可能，必须等加锁的线程释放锁之后才能继续执行下去，从而提高并发性能。

 

因为同步操作在Segment上，在执行map操作时，对key计算hash后，由于对不同的key计算出来的hash不可能都一样，从而落在不同的分段上，而能够并发执行。

 

 

 

 

 

 

 

 

 

构造Segment需要指定一个初始容量和一个加载因子，用于指定一个初始容量和设置一个threshold，在执行put操作时，如果map中元素的数目超过了这个threshold，执行rehash和扩容操作。

 

Threshold设置：

threshold = (int)(newTable.length * loadFactor);

 

 

Segment构造：

Segment(int initialCapacity, float lf)

 

Segment最大容量为1 << 30，也就是2的30次方。

static final int MAXIMUM_CAPACITY = 1 << 30;

 

The maximum capacity, used if a higher value is implicitly specified by either of the constructors with arguments. MUST be a power of two <= 1<<30 to ensure that entries are indexable using ints.

这个是Segment中桶的最大容量，但并不是最大可put的元素的最大数量。最大可put的元素的数量为int的最大值，即2的31次方－1。

 

计算落桶的位置：

int index = hash & (tab.length - 1);

 

和普通的HashMap及ConcurrentHashMap一样，默认的初始容量为16；默认的加载因子为0.75。

 

关键字比较：

e.hash != hash || !key.equals(e.key)

 

删除remove操作：

V remove(Object key, int hash, Object value)

如果value为null，则只匹配key，否则同时匹配key和value。

 

HashSet

 

HashSet，虽然带有Hash，但其实是一种集合，HashSet是Java中最基本的一个集合实现。我们没有在集合中过多的讲哈希表这种结构，包括HashMap等，因为它们都实现的是Map接口，而不是Collection接口。从Java的角度看，像HashMap等这种并不认为是一种集合。