未分类

Look HashMap Carefully!

HashMap的基础回顾:

  1. HashMap实现于Map接口
  2. HashMap采用key-value方式进行数据存储
  3. HashMap存储的数据没有顺序性
  4. HashMap是线程不安全的
  5. JDK1.7版本中,HashMap底层是“数组+链表”,通过建立pos=key%size这样的关系去为hashMap插入存储;pos求余就是数组下标。1.8多加了红黑树
  6. HashMap里边的数组初值是16个空间。数组里存放的就是链表的引用地址。
  7. 数组中某个位置上关联的链表存储的数据个数大于等于8时,HashMap就把链表改变为红黑树,要是桶中的值数又由多变少,至到为6个,那就又变回链表。static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
  8. 对象也可以作为hashMap的键,任何类都可以,主要它覆盖了hashCode()和equals()方法,hashCode方法用于向HashMap中插入键,而equals()方法用于从HashMap中检错值。
  9. HashMap中只允许一个空键。如果HashMap的键是空的,那么它将始终存在于索引0中。如果试图在空键上调用hashCode()方法,则会抛出NullPointerException。

各种前菜:

HashMap的迭代用法

使用keySet()和iterator()

  Set<String> keySet = map.keySet();
 Iterator<String> keySetIterator = keySet.iterator();
      while(keySetIterator.hasNext()) {
           String key = keySetIterator.next();
           System.out.println("key: " + key + " value: " +             map.get(key));
}

使用entrySet()和增强的for循环

for (String key : map.keySet()) {
   System.out.println("key: " + key + " value: " + map.get(key));
}

使用entrySet()和iterator()

 Set<Map.Entry<String, Object>> entrySet2 = map.entrySet();
Iterator<Map.Entry<String, Object>> entryIterator =     entrySet2.iterator();
while (entryIterator.hasNext()) {
    Map.Entry<String, Object> entry = entryIterator.next();
     System.out.println("key: " + entry.getKey() + " value: " + map.get(entry.getKey()));
}

使用keySet()和get()方法

Set<Map.Entry<String, Object>> entrySet = map.entrySet();
for (Map.Entry entry: entrySet) {
  System.out.println("key: " + entry.getKey() + " value: " + map.get(entry.getKey()));
      }

HashMap和HashTable的区别?

  • 最大区别就是HashMap能够容纳key为null或者value为null的,但是HashTable不可以。
  • HashTable是同步的,HashMap不是同步的,也就意味着其线程不安全
  • HashMap会比HashTable更快,因为HashMap不是同步的。

HashMap和ArrayList的区别?

  • 实现:Java中HashMap实现Map接口,ArrayList实现List接口
  • 存储对象:HashMap存储key和value两个对象,ArrayList只存储一个对象。
  • 排序:HashMap不提供排序保证,而ArrayList维护插入它们的对象的顺序。
  • 重复:HashMap不允许重复键,尽管它允许重复值,而ArrayList允许重复。
  • Equals和Hashcode方法:HashMap和ArrayList之间的第五个区别是,HashMap的键必须实现Equals()和Hashcode()方法,而ArrayList则不必实现这些方法。
  • get()方法性能:HashMap和ArrayList的第六个区别是,HashMap get(key)方法的性能在最好的情况下是O(1),在最坏的情况下是O(n),而ArrayList get(index)方法的性能总是O(1)。

各种领悟+源码:

HashMap中的数组是在何时进行初始化的?

虽然HashMap有四种构造方法,但是里面并没有定义数组初始化的代码。实际是在put方法里才会初始化数组。生当第一次调用put时,他首先会判断底层数组是否被初始化,如果没有初始化,则先进行初始化:

//构造方法里的赋值操作,没有看到定义数组的代码
public HashMap() {
   this.loadFactor = DEFAULT_LOAD_FACTOR; //赋值操作
}
//put方法里的初始化数组部分
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;

我们的HashMap的工作原理?

1.HashMap是基于hash算法产生一个集合工具类。

2.HashMap采用key-value键值对方式进行数据存储。

static class Node<K,V> implements Map.Entry<K,V> {

       final int hash;
       final K key;
       V value;
       Node<K,V> next;

       Node(int hash, K key, V value, Node<K,V> next) {
           this.hash = hash;
           this.key = key;
           this.value = value;
           this.next = next;
}

3.当通过HashMap中put方法存入键值对时,首先通过hash函数(由Object类继承而来)计算key关联的hashcode值。通过hashcode值确定数据bucket中位置(A bucket is used to store key value pairs .bucket就是存储许多键值对的)。在确认位置之后将key-value封装的Entry对象存储到此bucket中(或者出现覆盖操作)。

tab[i] = newNode(hash, key, value, null);
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
afterNodeAccess(e);

4.当通过hashMap的get(key k)方法读取值时,首先通过hashCode方法将key转换成hashcode,然后在bucket上找到对应位置上的Entry对象读取并输出Entry对象里放的value值,否则返回null。

return (e = getNode(hash(key), key)) == null ? null : e.value;
//👇first node 不是的话就循环找了
do {
    if (e.hash == hash &&
    ((k = e.key) == key || (key != null && key.equals(k))))
    return e;
} while ((e = e.next) != null);

hash碰撞以及解决方案?

hash碰撞就是我和你都需要在这个bucket里存着。使用put方法来保存数据时,将数据中的KEY转换为hash值,再根据hash值定位数组存放位置,若当前数组的位置上已经存在链表并且新数据key与链表上节点的key不同,此时遍历链表节点,找到相同的覆盖,不同的则将新数据作为最后一个节点存储在链表的最后一个位置。

hash碰撞存在的问题就是链表可能会很长。数据量大可能还要等待,因为要不断去遍历会导致存放速度就会变慢。解决方案呢就是开放地址方案链表算法方案

开放地址方案(Open Addressing)确保数组存放就是key-value,而不是键值对(散列表)。也就是改变之前那种“二维”的感觉,这就是一维的。如果要存入数据key对应的hash值在数组中位置上已经存在了数据,则通过数学算法对key进行新的运算得到新的hash值,就是新的数组位置,将新数组存入到数组新位置。不同的 key 会生成不一样的探测序列,也可以想象成是一种虚拟链条。

root = hash(key) % m   // 第一个位置,m 为数组的长度
index_i = (root + p(key, i)) % m  // 链条中的第 i 个位置

index_1 = (root + p(key, 1)) % m
index_2 = (root + p(key, 2)) % m
...

链表算法方案就是取单向链表代替散列表。当存入数据的key与链表第一个数据key不同相同时,向第一个数据next指针指向新数据。将数据next指针指向第二个数据位置,这个比较好理解,就是纯纯的链表,数据元素的逻辑顺序通过链表中的指针链接次序实现的。

get()时,要是两个不同key计算的hashcode相等时怎么办?怎么辨别我要取的是哪个value?

equals()方法来救场!虽然我们都对应着一个bucket,但是不要忘记了bucket是一个链表。而且它不是java.util.LinkedList中的那个LinkedList——它是一个单独的实现,仅用于映射的表。所以我们去遍历链表,使用keys.equals()方法比较存储好的键值,直到遇到相等的,也就是返回true了,那么这时候再返回相应的value值就好啦~

这个现象也叫做碰撞效应:如果两个对象拥有相等的hashcode。此时在bucket上存储位置一定是相同的,此时hashMap采用链表形式存储两个对象,就好比说在第一个Entry对象后放一个指针。

两个对象的hashCode相等时,她们的key未必相等,但是要是都相等,那就overrides吧~如果您试图存储HashMap中已经存在的键,那么它将用新值覆盖旧值,HashMap的大小也不变。这就是为什么当你在HashMap上调用keySet()方法来获取所有键时,它将返回Set而不是Collection,因为Set不允许重复。

还是总结一下:

  1. HashMap通过hash函数计算出key对应的HashCode
  2. HashMap通过HashCode定位bucket上存储位置(数组下标)
  3. 如果数组下标对应链表,此时HashMap遍历链表中每一个Entry对象
  4. 在遍历过程中,HashMap使用equals方法检测当前Entry对象中key去传入可以是否相等,如果相等读取Entry中value值。

如何衡量HashMap的性能呢?

根据Oracle Java文档,HashMap实例有两个影响其性能的参数:初始容量负载因子。容量是哈希表中的桶数,初始容量只是创建哈希表时的容量。

负载因子是衡量散列表容量自动增加之前允许其达到的满度。当哈希表中的条目数量超过负载因子和当前容量的乘积时,将对哈希表进行重新哈希(即重建内部数据结构),以便哈希表的桶数量大约是当前的两倍。

在HashMap类中,load factor的默认值是(.75)。

static final float DEFAULT_LOAD_FACTOR = 0.75f;//装载因子

HashMap的扩容机制

  1. HashMap默认容量是16,就是初始化的时候开辟了16块内存。
  2. HashMap默认负载因子是我们说的0.75
  3. HashMap在调用put方法时,如果发现HashMap中bucket占用率到16*0.75值则进行扩容
  4. HashMap在扩容后其容量达到原始容量2倍
  5. HashMap在扩容后通过重新计算entry对象在bucket中存储位置//hashcode是这么计算来的:异或,经过异或,可以提高hash值的散列度

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 newCap = DEFAULT_INITIAL_CAPACITY;//16
 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12(2的倍数避免内存碎片,可以减少冲突,移位操作效率也高)
 threshold = newThr; //12
(p = tab[i = (n - 1) & hash]) //做与运算

  //扩容
if(--size > threshold)  resize();

HashMap为什么要进行扩容?

HashMap进行扩容操作时并不是为了存储更多数据。HashMap进行扩容时为了减少碰撞几率,来提供HashMap运行效率。因为经常发生碰撞几率的时候,是要去遍历链表的,这样就增加了时间。

HashMap扩容时会出现什么问题?

  • 在单线程情况下,HashMap扩容时对运行效率产生降低问题,就不会有其他问题。
  • 多线程情况下,产生竞条件(race condition)进而导致死循环。假设线程a和线程b在同一时刻下都认为当前HashMap进行扩容,扩容链表中Entry对象存放顺序会反过来,此时Entry对象新的Bucket位置上从链表中第一个位置开始重新存储。HashMap这样做的本次防止出现尾部遍历地场景。当时此时如果线程a和线程b都要将自己的管理的Entry存入到同一个链表中第一个位置,此时出现竞争条件进行产生了死循环。
  • 在多线程的情况下,不能使用HashMap

参考链接:

🎈 Hashing :How HashMap Works In Java Or How Get() Method Works Internally

🎈 hash结构的另一种形式——开放地址法

发表评论

邮箱地址不会被公开。 必填项已用*标注