hashmap面试问题

基于哈希表实现的 Map 接口。此实现提供了所有可选映射操作，并容许空值 (value) 和空键 (key)。(HashMap 类大抵相当于 Hashtable，只是它是线程不平安的，并且容许空值) 这个类不能保障映射的程序; 特地是, 它不能保障程序随工夫放弃不变。

hashmap 底层由数组和链表实现(jdk1.8 中当链表的长度大于 8 时, 链表会转换成红黑树)

初始容量 16

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

最大容量 1 << 30

static final int MAXIMUM_CAPACITY = 1 << 30;

// 为什么不是 1 << 31, 因为最左侧的一位示意符号位, 容量不能为正数

放慢 hash 计算速度
均匀分布，缩小 hash 抵触

// 计算索引算法
i=(len - 1) & hash

len 为数组的长度, 因为 len 是 2 的 n 次方,(n-1)转换成 2 进制后全副为 1.

2 的 n 次方，能够通过位移操作来实现，能够放慢 hash 计算速度，联合按位与计算放慢数组下标的计算。例如在 HashMap 做扩容时，满足 2 的幂就是相当于每次扩容都是翻倍（就是 <<1 右移一位），这样扩容时在从新计算下标地位时，只有两种状况，一种是下标不变，另一种是下标变为：原下标地位 + 扩容前容量，这样扩容后节点挪动绝对较少，也能够进步性能。。

能够改善数据的均匀分布，缩小 hash 抵触，毕竟 hash 抵触越大，代表数组中一个链的长度越大，这样的话会升高 hashmap 的性能。
其中要害代码为 HashMap 中的数组下标计算：i = (n – 1) & hash，该计算方法能够实现一个均匀分布。

高 16 位和低 16 位进行异或

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

次要还是为了解决 hash 碰撞问题。让高位和低位都参加 hash 值的计算

new HashMap<>(n);

保障输出的值是 2 的 n 次方, 该算法让最高位的 1 前面的位全变为 1

// 返回大于输出参数且最近的 2 的整数次幂的数。比方 10，则返回 16

// Returns a power of two size for the given target capacity.

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

加载因子 0.75. 如果默认容量是 16, 那么当元素达到 16 x 0.75=12 时, 就会产生扩容.

static final float DEFAULT_LOAD_FACTOR = 0.75f;

在 HashMap 的源码中有这么一段正文

* Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
* 0:    0.60653066
* 1:    0.30326533
* 2:    0.07581633
* 3:    0.01263606
* 4:    0.00157952
* 5:    0.00015795
* 6:    0.00001316
* 7:    0.00000094
* 8:    0.00000006
* more: less than 1 in ten million

大略意思是:

在现实状况下，应用随机哈希码，在扩容阈值（加载因子）为 0.75 的状况下，节点呈现在频率在 Hash 桶（表）中遵循参数均匀为 0.5 的泊松散布。疏忽方差，即 X = λt，P(λt = k)，其中 λt = 0.5 的状况，按公式

抉择 0.75 作为默认的加载因子，齐全是工夫和空间老本上寻求的一种折衷抉择。

static final int TREEIFY_THRESHOLD = 8;

当 put 时，如果发现目前的 bucket 占用水平曾经超过了 Load Factor 所心愿的比例，那么就会产生 resize。在 resize 的过程，简略的说就是把 bucket 裁减为 2 倍，之后从新计算 index，把节点再放到新的 bucket 中。resize 的正文是这样形容的：当超过限度的时候会 resize，然而又因为咱们应用的是 2 次幂的扩大(指长度扩为原来 2 倍)，所以，元素的地位要么是在原地位，要么是在原地位再挪动 2 次幂的地位。

例如咱们从 16 扩大为 32 时，具体的变动如下所示：

因而元素在从新计算 hash 之后，因为 n 变为 2 倍，那么 n - 1 的 mask 范畴在高位多 1bit(红色)，因而新的 index 就会产生这样的变动：

因而，咱们在裁减 HashMap 的时候，不须要从新计算 hash，只须要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成“原索引 +oldCap”。能够看看下图为 16 裁减为 32 的 resize 示意图：

这个设计的确十分的奇妙，既省去了从新计算 hash 值的工夫，而且同时，因为新增的 1bit 是 0 还是 1 能够认为是随机的，因而 resize 的过程，平均的把之前的抵触的节点扩散到新的 bucket 了。

 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) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                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;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

通过对 key 的 hashCode()进行 hashing，并计算下标 ( n-1 & hash)，从而取得 buckets 的地位。如果产生碰撞，则利用 key.equals() 办法去链表或树中去查找对应的节点

jdk1.7 插入元素到单链表中采纳头插法，jdk1.8 采纳的是尾插法。

jdk1.7 插入链表的头部, 有一种认识是新插入的数据被查问的概率比拟大, 插入到头部查问绝对比拟快. 然而在多线程环境中扩容可能会造成循环链表, 导致 CPU100%
jdk1.8 改良: 采纳尾插法, 在扩容时不必从新计算 hash 值, 元素索引值的变换是有法则的.

jdk1.7 一对 key,value 叫做 Entry
jdk1.8 一对 key,value 叫做 Node

hashCode 决定了 Node/Entry 在数组中的地位
equals 在元素产生碰撞时比拟应用

hashmap 默认应用 java.lang.Object#equals 比照的是对象的地址,hashmap 对象存储堆中, 地址必定不一样, 所以要依据业务实现本人的 equals, 然而 equals 判断须要, 然而 hashmap 在判断是先判断 hashCode 相等后才会去执行 equals.

 if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
....

案例

public class Name {

  private String first; //first name
  private String last;  //last name

  public String getFirst() {return first;}

  public void setFirst(String first) {this.first = first;}

  public String getLast() {return last;}

  public void setLast(String last) {this.last = last;}

  public Name(String first, String last) {
    this.first = first;
    this.last = last;
  }

  @Override
  public boolean equals(Object object) {System.out.println("equals is running...");
    Name name = (Name) object;

    return first.equals(name.getFirst()) && last.equals(name.getLast());
  }

  public static void main(String[] args) {Map<Name, String> map = new HashMap<Name, String>();
    Name n1 = new Name("mali", "sb");
    System.out.println("the hashCode of n1 :" + n1.hashCode());
    map.put(n1, "yes");
    Name n2 = new Name("mali", "sb");
    System.out.println("the hashCode of n2 :" + n2.hashCode());
    System.out.println("is the key existed? ture or false? ->"
        + map.containsKey(n2));
  }

}

原文: https://rumenz.com/rumenbiji/java-hashmap-interview.html

hashmap面试问题

jdk1.8 对 hashmap 的简略介绍

hashmap 底层构造

hashmap 的初始容量和最多容量

为什么规定容量必须是 2 的 n 次幂

hashmap 怎么计算 hash 值, 为什么

怎么指定 hashmap 的初始值, 怎么保障输出的值是 2 的 n 次方

hashmap 在什么状况下进行扩容

为什么加载因子是 0.75

在 jdk1.8 中在什么状况下链表会转换成红黑树

jdk1.8 resize 的过程

你晓得 get 和 put 的原理吗？equals()和 hashCode()的都有什么作用？

头插法与尾插法

Entry 与 Node

为什么要重写 equals 和 hashCode