欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java HashMap内部实现原理详解

程序员文章站 2024-03-08 11:16:28
详解hashmap内部实现原理 内部数据结构 static class entry implements map.entry

详解hashmap内部实现原理

内部数据结构

static class entry<k,v> implements map.entry<k,v> {
    final k key;
    v value;
    entry<k,v> next;
    int hash;

从上面的数据结构定义可以看出,hashmap存元素的是一组键值对的链表,以什么形式存储呢

transient entry<k,v>[] table = (entry<k,v>[]) empty_table;

可以看出,是以数组形式储存,好的,现在我们知道,hashmap是以数组形式存储,每个数组里面是一个键值对,这个键值对还可以链接到下个键值对。如下图所示:

java HashMap内部实现原理详解

hashmap的添加

public v put(k key, v value) {
    if (table == empty_table) {
      inflatetable(threshold);
    }
    if (key == null)
      return putfornullkey(value);
    int hash = hash(key);
    int i = indexfor(hash, table.length);
    for (entry<k,v> e = table[i]; e != null; e = e.next) {
      object k;
      if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        v oldvalue = e.value;
        e.value = value;
        e.recordaccess(this);
        return oldvalue;
      }
    }

    modcount++;
    addentry(hash, key, value, i);
    return null;
  }

这里可以看出,hashmap的添加,首先根据一个entry的hash属性去查找相应的table元素i,然后看这个位置是否有元素存在,如果没有,直接放入,如果有,遍历此次链表,加到表尾

删除

final entry<k,v> removeentryforkey(object key) {
    if (size == 0) {
      return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    int i = indexfor(hash, table.length);
    entry<k,v> prev = table[i];
    entry<k,v> e = prev;

    while (e != null) {
      entry<k,v> next = e.next;
      object k;
      if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k)))) {
        modcount++;
        size--;
        if (prev == e)
          table[i] = next;
        else
          prev.next = next;
        e.recordremoval(this);
        return e;
      }
      prev = e;
      e = next;
    }

    return e;
  }

删除的话,还是先根据hash在table数组中查找,然后再根据equals在链表中进行查找,这个也是为什么hashmap和hashset等以hash方式进行存储的数据结构要求实现两个方法hashcode和equalsd的原因

学过hash的人都知道,hash表的性能和hash冲突的发生次数有很大关系,但有不能申请过长的table表浪费空间,所以这里有了我们的resize函数

扩容机制

void resize(int newcapacity) {
    entry[] oldtable = table;
    int oldcapacity = oldtable.length;
    if (oldcapacity == maximum_capacity) {
      threshold = integer.max_value;
      return;
    }

    entry[] newtable = new entry[newcapacity];
    transfer(newtable, inithashseedasneeded(newcapacity));
    table = newtable;
    threshold = (int)math.min(newcapacity * loadfactor, maximum_capacity + 1);
  }

这个方法会在put的时候调用,上面put的时候先调用 addentry(hash, key, value, i);方法,然后看addentry方法

void addentry(int hash, k key, v value, int bucketindex) {
    if ((size >= threshold) && (null != table[bucketindex])) {
      resize(2 * table.length);
      hash = (null != key) ? hash(key) : 0;
      bucketindex = indexfor(hash, table.length);
    }

    createentry(hash, key, value, bucketindex);
  }

上面可以看出那么 hashmap 当 hashmap 中的元素个数超过数组大小 *loadfactor 时,就会进行数组扩容,loadfactor 的默认值为 0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为 16,那么当 hashmap 中元素个数超过 16*0.75=12 的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位 置,而这是一个非常消耗性能的操作,所以如果我们已经预知 hashmap 中元素的个数,那么预设元素的个数能够有效的提高 hashmap 的性能。

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!