HashMap面试题

Posted on Edited on

JDK7

  1. 域变量
    默认初始大小：16
    最大长度：1 << 30
    默认加载因子：0.75f
    modCount: 对Map的iterator()操作做一致性校验，如果在iterator操作过程中，map的数值有修改，直接抛出ConcurrentModiifcationException异常
    threshold: table.length * loadFactor。

  2. put()方法

    • 如果Key为null，统一放在下标为0的bucket，即table[0]位置的链表，如果是第一次对key=null做put操作，将会在table[0]的位置新增一个Entry节点，使用头插法做链表插入。调用的是putForNullKey()方法:首先选择table[0]位置的链表，然后对链表做遍历操作，如果有节点的key为null，则用新值覆盖旧值，并且返回旧值，否则新增一个key为null的Entry节点。

  3. 扩容

    • 扩容后的大小是扩容前的两倍
    • 将数据从旧table迁移到扩容后的新table。为避免碰撞过多，先决策是否需要对每个Entry链表节点重新hash，然后根据hash值计算得到bucket下标，然后用头插法做节点迁移。

  4. hash值的计算

    • 使用key的hashCode作为算式(arithmetic)的输入，得到了hash值。
    • 对于两个对象，如果hashCode相同，那么hash值就一定相同。
    • 如果两个对象逻辑相等（内存地址相同），那么hashCode一定相等，反之不一定成立。

  5. bucket下标的计算

    • 取模：h & (length-1) h为hashCode
  6. hashCode()和hash值
    • Java中hashCode()方法是用来生成hashCode值,hashCode值是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。
    • 把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是哈希值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。

  7. 为什么HashTable的大小控制为2的幂次数

    • 降低碰撞的概率，使散列更均匀，根据bucket下标的计算公式，当哈希表的长度为2的次幂时，等同于使用表长度对hash值取模，散列更均匀。
    • 表的长度为2的次幂，那么(length-1)的二进制最后一位一定是1，在对hash值做“与”运算时，最后一位就可能是1也可能是0，换句话说取模的结果既有奇数又有偶数。
    • 此时h & (length-1)就是h % length

  8. get()方法

    • 通过key的hash值计算bucket的下标，然后遍历对应bucket上的链表，得到结果。

  9. 遍历Map的方式

    • Iterator迭代器
    • for(Map.Entry entry : testMap.entrySet())
    • foreach(JDK1.8才有，不推荐，因为底层就是方式2)
    • 获取keySet()的迭代器遍历
      以上的底层都是迭代器

  10. Iterator的实现

    • HashMap中增加了一个内部类HashIterator，循环哈希table，直到找到不为空的bucket为止。

  11. fail-fast策略

    • 在系统设计中，当遇到可能会诱导失败的条件时立即上报错误。
    • modCount域变量用于实现hashMap中的fail-fast。

JDK8

相比与JDK7，JDK8中的HashMap会将较长的链表(大于8)转为红黑树。

  1. put()

    • 在JDK7中，新增节点使用的是头插法，但在JDK8中，在链表使用尾插法，防止死链。
    • 若hashTable为null或长度为0，则扩容。
    • 根据index找到bucket，若bucket上没有节点，那么直接新增一个节点，赋给bucket。
    • 若当前bucket上有链表，且头节点匹配，则直接替换。
    • 若当前bucket上为树结构则转为红黑树的插入操作。
    • 若以上都不成立，则对链表进行遍历：有则替换，无则末尾添加。
    • 如果链表长度大于TREEIFY_THRESHOLD，则执行红黑树转换操作。

  2. 扩容

    • 如果hashTable为null或长度为0，如果Map中存储的k-v对数量超过了threshold，则触发扩容
    • 不同于JDK7，JDK8在做数据迁移的时候保持了顺序(preserve order)
    • 新的索引值要么和原来的索引值一样，要么是原索引值的两倍，因为h & (length-1)中length-1的低位全是1。例如原先的hashCode为:1010 … 11101(共32位)，将长度从16扩容到32，length-1从1111变为11111，然后根据公式做按位与，得出的结果后四位是一样的，第一位取决于hashCode对应位置上的值。

  3. get()

    • 根据key计算hash值，进一步计算得到hashTable的目标index，若此bucket上为红黑树，则在红黑树上查找，否则遍历链表。

HashMap、HashTable

  1. HashMap vs HashTable

    • HashMap is non synchronized. It is not-thread safe and can’t be shared between many threads without proper synchronization code whereas Hashtable is synchronized. It is thread-safe and can be shared with many threads.
    • HashMap allows one null key and multiple null values whereas Hashtable doesn’t allow any null key or value.
    • HashMap is generally preferred over HashTable if thread synchronization is not needed

  2. Why HashTable doesn’t allow null and HashMap does?
    To successfully store and retrieve objects from a HashTable, the objects used as keys must implement the hashCode method and the equals method. Since null is not an object, it can’t implement these methods. HashMap is an advanced version and improvement on the Hashtable. HashMap was created later.

  3. Why HashMap is not thread-safe?

    • Ideologically
      A hash map is based on an array, where each item represents a bucket. As more keys are added, the buckets grow and at a certain threshold the array is recreated with a bigger size, its buckets rearranged so that they are spread more evenly (performance considerations).

    • Technically
      It means that sometimes HashMap#put() will internally call HashMap#resize() to make the underlying array bigger.

    • HashMap#resize() assigns the table field a new empty array with a bigger capacity and populates it with the old items. While this population happens, the underlying array doesn’t contain all of the old items and calling HashMap#get() with an existing key may return null.

其他

  1. HashCode怎么算的?
    • memory reference of object in integer form
  2. equals()
    • compare the key whether the are equal or not

Q. What is difference between HashMap and Hashtable?

HashMap and Hashtable both are used to store data in key and value form. Both are using hashing technique to store unique keys.

Sl.No HashMap Hashtable
01. HashMap is non synchronized. It is not-thread safe and can’t be shared between many threads without proper synchronization code. Hashtable is synchronized. It is thread-safe and can be shared with many threads.
02. HashMap allows one null key and multiple null values. Hashtable doesn’t allow any null key or value.
03. HashMap is a new class introduced in JDK 1.2. Hashtable is a legacy class.
04. HashMap is fast. Hashtable is slow.
05. We can make the HashMap as synchronized by calling this code Map m = Collections.synchronizedMap(hashMap); Hashtable is internally synchronized and can’t be unsynchronized.
06. HashMap is traversed by Iterator. Hashtable is traversed by Enumerator and Iterator.
07. Iterator in HashMap is fail-fast. Enumerator in Hashtable is not fail-fast.
08. HashMap inherits AbstractMap class. Hashtable inherits Dictionary class.