# Maps

## HashMap

**存储结构**\
![](/files/-M1JIW8VxqBrhUaqGXhR)

左侧是一个数组，数组的每个成员是一个链表，每个元素都包含着一个指针，用于元素之间的连接。Hash函数根据Object的性质将Object插入到其中去，同理也从中寻找取出。

### Java 7

```java
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    // 下面进行的是一个hash的扰乱
    // 因为在下面我们直接与 length-1 与操作
    // 如果不进行扰动会导致高位的贡献为0
    // 所以这里是将高位部分 (h>>>20) 和中间位 (h>>>12)
    // 和低位都进行了一个计算最后得到我们的数值
    h ^= k.hashCode(); 
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

// indexFor函数获取当前的Object插入的下标  
// 由于 Java 中初始化和扩容hash存储的数组都是 2的幂次
// 所以直接用 & (2^n-1) 代替 % 2^n 的操作
// 还有一个好处就是，取模操作对负数的支持不好
// 直接与操作保证了不会出现负数，无需考虑数组越界
static int indexFor(int h, int length) {
    return h & (length-1);
}
```

### Java8

```java
static final int hash(Object key) {
    int h;
    // 追求速率，直接一次高位与低位的异或混合，而不是四次
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```

## ConcurrentHashMap

### Java7

```java
private int hash(Object k) {
    int h = hashSeed;

    if ((0 != h) && (k instanceof String)) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // Spread bits to regularize both segment and index locations,
    // using variant of single-word Wang/Jenkins hash.
    h += (h <<  15) ^ 0xffffcd7d;
    h ^= (h >>> 10);
    h += (h <<   3);
    h ^= (h >>>  6);
    h += (h <<   2) + (h << 14);
    return h ^ (h >>> 16);
}

int j = (hash >>> segmentShift) & segmentMask;
```

### Java8

Java 8 里面的求hash的方法从hash改为了spread。

```java
static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}
```

## HashTable (线程安全)

### Java7

```java
private int hash(Object k) {
    // 简单进行hash，并取其hashCode
    // hashSeed will be zero if alternative hashing is disabled.
    return hashSeed ^ k.hashCode();
}

// 没有单独的 indexOf() 只有下面的：
// 和 0x7FFFFFFF 进行与操作是为了避免出现负数求模
int index = (hash & 0x7FFFFFFF) % tab.length;
```

**为什么HashTable的hash函数和取模都采用的是最简单的方式？**

> 需要考虑到 HashTable 的构造函数和扩容函数：\
> HashTable默认的初始大小为11，之后每次扩充为原来的2n+1。 也就是说，HashTable的链表数组的默认大小是一个素数、奇数。之后的每次扩充结果也都是奇数。 由于HashTable会尽量使用素数、奇数作为容量的大小。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。 详细的论证：[Link](http://zhaox.github.io/algorithm/2015/06/29/hash)

## Reference

1. [Hollis | 全网把Map中的hash()分析的最透彻的文章，别无二家。](http://www.hollischuang.com/archives/2091) &#x20;


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://legacy.cookielau.com/archives/2-java/2-mapcontainer.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.