JavaHashMap 구현 원리에 대한 자세한 설명

HashMap은 해시 테이블을 기반으로 하는 Map 인터페이스 구현입니다. 이는 모든 선택적 매핑 작업을 제공하고 null 값 및 null 구성의 사용을 허용하며 동기화되지 않으며 매핑 순서를 보장하지 않습니다. HashMap의 구현 원리에 대한 연구를 기록해 보겠습니다.

HashMap 내부 저장소

HashMap 내부에는 임시 변수 배열 테이블(버킷이라고도 함)을 유지하여 모든 키-값 쌍 관계가 저장됩니다. 버킷의 크기는 필요에 따라 크기를 조정할 수 있으며 길이는 2의 거듭제곱이어야 합니다. 다음 코드:

/**
  * 一个空的entry数组，桶 的默认值
  */
 static final Entry<?,?>[] EMPTY_TABLE = {};
 /**
  * 桶，按需调整大小，但必须是2的次幂
  */
 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

초기 용량 및 부하율

HashMap에는 성능, 초기 용량 및 부하율에 영향을 미치는 두 가지 매개 변수가 있습니다. 용량은 해시 테이블의 버킷 수이고, 초기 용량은 단순히 해시 테이블이 생성될 때의 해시 테이블 용량이며, 부하율은 해시 테이블의 용량이 자동으로 증가하기 전에 해시 테이블이 얼마나 가득 찰 수 있는지를 측정한 것입니다. 해시 테이블의 항목 수가 로드 팩터와 현재 용량의 곱을 초과하는 경우 해시 테이블을 다시 해시해야 하며(즉, 내부 데이터 구조가 재구성됨) 현재 용량의 두 배로 새 항목이 생성됩니다. 재건축 중. 초기 용량과 부하율은 생성자를 통해 설정할 수 있습니다. 기본 초기 용량은 16개 항목이고, 최대 용량은 2^30개 항목이며, 기본 부하율은 0.75입니다.

버킷은 버킷과 같습니다. 기본 초기 물 저장 용량은 16 단위입니다. 기본적으로 물이 16*0.75 로 채워지면 다음 데이터가 추가될 때 용량이 먼저 32 단위로 확장됩니다. 0.75는 부하율이며, 버킷 생성 시 초기 용량과 부하율을 설정할 수 있습니다. 양동이의 최대 용량은 물 30단위의 2제곱입니다. 초기 용량 설정 수량이 최대 용량보다 클 경우 최대 용량이 우선합니다. 확장시 최대 용량 이상일 경우 바로 반환됩니다.

다음은 기본 초기 용량, 부하율 및 기타 상수를 정의하는 HashMap 소스 코드의 일부입니다.

/**
  * 默认初始化容量，必须为2的次幂The default initial capacity - MUST be a power of two.
  */
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 /**
  * 最大容量，如果通过构造函数参数中传递初始化容量大于该最大容量了，也会使用该容量为初始化容量  * 必须是2的次幂且小于等于2的30次方  */
 static final int MAXIMUM_CAPACITY = 1 << 30;
 /**
  * 默认的负载因子，可以通过构造函数指定
  */
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 /**
  * 一个空的数组表，当 桶没有初始化的时候
  */
 static final Entry<?,?>[] EMPTY_TABLE = {};
 /**
  * 桶 , 存储所有的键值对条目，可以按需调整大小，长度大小必须为2的次幂
  */
 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
 /**
  * Map中键值对的数量，在每次新增或删除的时候都会对size进行+1或者-1操作.
  */
 transient int size;
 /**
  * 负载值，需要调整大小的临界值，为：(capacity * load factor).在每次调整大小后会使用新的容量计算一下
  * @serial
  */
 // If table == EMPTY_TABLE then this is the initial capacity at which the
 // table will be created when inflated.
 int threshold;
 /**
  * 负载因子，如果构造函数中没有指定，则采用默认的负载因子，
  *
  * @serial
  */
 final float loadFactor;
 /**
  * HashMap结构修改次数，结构修改时改变HashMap中的映射数量或修改其内部结构（例如，* rehash方法，重建内部数据结构），此字段用于在  * HashMap的集合视图上生成的迭代器都处理成快速失败的
  */
 transient int modCount;

초기 용량 및 부하율 성능 조정

보통 기본 부하 계수(0.75)는 시간과 공간 비용 간의 절충안을 추구합니다. 로드 비율이 너무 높더라도 공간 오버헤드는 줄어들지만 쿼리 비용도 증가합니다(이는 get 및 put 작업을 포함한 대부분의 HashMap 클래스 작업에 반영됩니다). 재해시 작업 수를 최소화하려면 초기 용량을 설정할 때 맵에 필요한 항목 수와 해당 로드 요소를 고려해야 합니다. 초기 용량이 최대 항목 수를 로드 비율로 나눈 값보다 크면 재해시 작업이 발생하지 않습니다.

HashMap 인스턴스에 많은 매핑 관계를 저장하려는 경우 충분히 큰 초기 용량으로 생성하면 테이블의 효율적인 저장 용량을 늘리기 위해 필요에 따라 자동 재해시 작업을 수행하는 것보다 매핑 관계가 더 효율적이 됩니다.

다음은 HashMap 데이터 구조를 재구성하는 코드입니다.

void resize(int newCapacity) {
  Entry[] oldTable = table;
  int oldCapacity = oldTable.length;
  if (oldCapacity == MAXIMUM_CAPACITY) { // 如果容量已达最大限制，则设置下负载值后直接返回
   threshold = Integer.MAX_VALUE;
   return;
  }
  // 创建新的table存储数据
  Entry[] newTable = new Entry[newCapacity];
  // 将旧table中的数据转存到新table中去，这一步会花费比较多的时间
  transfer(newTable, initHashSeedAsNeeded(newCapacity));
  table = newTable;
  // 最后设置下下次调整大小的负载值
  threshold = (int) Math.min(newCapacity * loadFactor,
    MAXIMUM_CAPACITY + 1);
}

HashMap 구성 방법

4가지 구성 메서드는 기존 Map에서 새 HashMap을 생성합니다. 실제로 처음 세 가지 구성 메서드는 매개변수가 두 개 전달되지 않으면 궁극적으로 세 번째 메서드를 호출합니다. 사용된 수치와 코드는 다음과 같습니다.

/**
   * Constructs an empty <tt>HashMap</tt> with the default initial capacity
   * (16) and the default load factor (0.75).
   */
  public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
  }
  /**
   * Constructs an empty <tt>HashMap</tt> with the specified initial
   * capacity and the default load factor (0.75).
   *
   * @param initialCapacity the initial capacity.
   * @throws IllegalArgumentException if the initial capacity is negative.
   */
  public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }
  /**
   * Constructs an empty <tt>HashMap</tt> with the specified initial
   * capacity and load factor.
   *
   * @param initialCapacity the initial capacity
   * @param loadFactor   the load factor
   * @throws IllegalArgumentException if the initial capacity is negative
   *     or the load factor is nonpositive
   */
  public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
      throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
      initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
      throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
    this.loadFactor = loadFactor;
    threshold = initialCapacity;
    init();
  }

위에서 볼 수 있듯이 생성자에서는 초기 용량이 최대 용량보다 크면 바로 최대 용량으로 대체됩니다. .

put 메소드

HashMap의 더 중요한 부분을 살펴보겠습니다

/**
   * 在此映射中关联指定值与指定建。如果该映射以前包含了一个该键的映射关系，则旧值被替换
   *
   * @param 指定将要关联的键
   * @param 指定将要关联的值
   * @return 与key关联的旧值，如果key没有任何映射关系，则返回null（返回null还可能表示该映射之前将null与key关联）
   */
  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;
  }

1. 먼저 put 메소드에서 버킷이 기본인지 여부를 확인합니다. 초기화되지 않은 경우 inflateTable 메서드를 호출하여 초기화한 다음 매개변수 키가 null인지 확인합니다. null인 경우 putForNullKey를 호출하여 구체적으로 null 키로 데이터를 입력합니다. 아래 3단계와 같이 null 키가 있는 데이터의 기본 저장 위치는 첫 번째 위치입니다. 즉, 아래 첨자의 기본값은 0입니다.

2. 키가 null이 아닌 경우 hash() 메서드를 호출하여 키의 해시 값을 가져옵니다. 해시 값을 기준으로 버킷에서 키가 배치될 수 있는 위치를 계산할 수 있습니다. indexFor 메소드를 통해 버킷의 길이.

3. Entry 객체에는 next 속성이 있는데, 이는 동일한 해시 값을 가진 요소를 저장하기 위해 단방향 연결 목록을 구성할 수 있습니다. 따라서 계산된 키의 해시값이 반복되면 저장 위치도 반복되게 됩니다. 저장 위치에 있는 요소와 해당 요소의 다음 속성 목록이 주어진 키와 완전히 일치하는지 확인하면 됩니다. 키의 해시 값입니다. 완전히 일치하는 것이 있으면 이미 존재한다는 의미이므로 이전 값을 교체하고 이전 값을 반환 값으로 직접 반환합니다.

4. 구조 수정 횟수를 1만큼 늘립니다.

5. addEntry 메서드를 호출하여 HashMap에 새 키-값 쌍을 추가합니다. addEntity 메소드는 먼저 현재 항목 데이터가 부하 값(버킷 용량 * 부하 계수)보다 크거나 같은지 확인하고 버킷의 지정된 위치가 null보다 크고 지정된 위치가 null이 아닌 경우입니다. 버킷 용량을 현재 용량으로 2회 조정하세요. 버킷 용량을 조정하려면 위의 초기 용량 및 부하율 성능 조정 카탈로그를 참조하세요. 해시 값을 다시 계산하고 저장 위치를 ​​계산합니다. createEntry 메소드를 호출하고 버킷

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);
  }
  void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
  }
  /**
  * Entry构造方法，创建一个新的Entry.
  */
  Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
  }

에 저장합니다.

 6. 在 createEntry 方法中，首先获取指定位置的entry，然后新生成一个entry，在生成entry时把原有的entry存储到新生成的entry的next属性中（参考Entry的构造方法），并把指定位置的entry替换成新生成的。

因为新增条目的时候，需要计算hash值，长度不够时需要调整长度，当计算的存储位置已有元素的时候需要进行链表式的存储，所以使用HashMap新增操作的效率并不是太高。

get方法

首先看下get方法的源码：

/**
   * 返回指定键所映射的值；如果对于该键来说，此映射不包含任何映射关系，则返回null
   * 返回null值并不一定表明该映射不包含该键的映射，也可能改映射将该键显示的映射为null，可使用containsKey操作来区分这两种情况
   * @see #put(Object, Object)
   */
  public V get(Object key) {
    if (key == null)
      return getForNullKey();
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
  }
  final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
      return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
       e != null;
       e = e.next) {
      Object k;
      if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        return e;
    }
    return null;
}

 

get方法实现较简单，以下是几个步骤：

首先判断key是否为null，如果为null，则调用 getForNullKey 方法来获取，如果不为null则调用 getEntry 方法来获取。getForNullKey方法与getEntity基本上一致，只不过少了一个步骤，就是默认的key为null的存储位置在第一个，即下标为0，没有去计算位置而已。

getEntity方法根据key计算哈希值，然后用哈希值、桶的长度计算存储位置。

getEntity以获取指定位置的entry作为遍历的开始，遍历entry的next单链表，如果entry的哈希值与计算的哈希值一致且entry的key与指定的相等则返回entry

根据getEntity返回的值，get方法返回对应的值。

通过查看get的源码可以发现，get方法通过key的哈希值与桶的长度计算存储位置，基本上一下就能定位到要找的元素，即使再遍历几个重复哈希值的key，也是很快速的，因为哈希值相对唯一，所以HashMap对于查找性能是非常快的。

自定义对象作为HashMap的键

class User {
  // 身份证号码
  protected int idNumber;
  public User(int id){
    idNumber = id;
  }
}
public class TestUser{
  public static void main(String[] args) {
    Map<User, String> map = new HashMap<User, String>();
    for (int i=0; i<5; i++) {
      map.put(new User(i), "姓名: " + i);
    }
    System.out.println("User3 的姓名：" + map.get(new User(3)));
  }
}
输出：
User3 的姓名：null

如上代码，通过自定义的User类实例作为HashMap的对象时，在打印的时候是无法找到User3的姓名的，因为User类自动继承基类Object，所以这里会自动使用Object的hashCode方法生成哈希值，而它默认是使用对象的地址计算哈希值的。因此new User(3)生成的第一个实例的哈希值与生成的第二个实例的哈希值是不一样的。但是如果只需要简单的覆盖hashCode方法，也是无法正常运作的，除非同时覆盖equals方法，它也是Object的一部分。HashMap使用equals()判断当前的键是否与表中存在的键相同，可以参考上面的get或put方法。

正确equals()方法必须满足下列5个条件：---参考《Java编程思想》—489页

自反性。对任意x，x.equals(x)一定返回true

对称性。对任意x和y，如果有y.equals(x)返回true，则x.equals(y)也返回true

传递性。对任意x,y,z，如果有x.equals(y)返回true，y.equals(z)返回true，则x.equals(z)一定返回true

一致性，对任意x和y，如果对象中用于等价比较的信息没有改变，那么无论调用x.equals(y)多少次，返回的结果应该保持一致，要么一致是true，要么一致是false.

对任何不是null的x，x.equals(null)一定返回false

再次强调：默认的Object.equals()只是比较对象的地址，所以一个new User(3)并不等于另一个new User(3)。因此，如果要使用自己的类作为HashMap的键，必须同时重载hashCode()和equals().

如下代码可以正常运作：

 class User {
  // 身份证号码
  protected int idNumber;
  public User(int id){
    idNumber = id;
  }
  @Override
  public int hashCode() {
    return idNumber;
  }
  @Override
  public boolean equals(Object obj) {
    return obj instanceof User && (idNumber==((User)obj).idNumber);
  }
}
public class TestUser{
  public static void main(String[] args) {
    Map<User, String> map = new HashMap<User, String>();
    for (int i=0; i<5; i++) {
      map.put(new User(i), "姓名: " + i);
    }
    System.out.println("User3 的姓名：" + map.get(new User(3)));
  }
}
输出：
User3 的姓名：姓名: 3

上面只是简单的在hashCode中返回了idNumber作为唯一的判别，用户也可以根据自己的业务实现自己的方法。在equals方法中，instanceof会悄悄的检查对象是否为null，如果instanceof左边的参数为null，则会返回false，如果equals()的参数不为null且类型正确，则基于每个对象中的实际的idNumber进行比较。从输出可以看出，现在的方式是正确的。

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持PHP中文网！

更多详解JavaHashMap实现原理相关文章请关注PHP中文网！