java.util. HashMap

/**
 * Cached value of the alternative hashing algorithm result
 */
private transient int hash32 = 0;

/**
 * Calculates a 32-bit hash value for this string.
 *
 * @return a 32-bit hash value for this string.
 */
int hash32() {
  int h = hash32;
  if (0 == h) {
     // harmless data race on hash32 here.
     h = sun.misc.Hashing.murmur3_32(HASHING_SEED, value, 0, value.length);

     // ensure result is not zero to avoid recalcing
     h = (0 != h) ? h : 1;

     hash32 = h;
  }
  return h;
}

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *     <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *     (A <tt>null</tt> return can also indicate that the map
 *     previously associated <tt>null</tt> with <tt>key</tt>.)
 */
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);

  // table의 각 인덱스에는 Entry가 들어 있고, Entry는 LinkedList 이다.
  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;
}

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *     <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *     (A <tt>null</tt> return can also indicate that the map
 *     previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
         boolean evict) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;

  // 만약 테이블이 없다면, 비어 있는 테이블을 만든다
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

  // 테이블 인덱스는 (n-1) & hash 로 계산한다
  // p가 인덱스에 있는 노드를 참조하게 한다
  // p가 null이면 새로운 노드를 만들어 테이블 인덱스에 넣는다
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  else {
    Node<K,V> e; K k;
    if (p.hash == hash &&
      ((k = p.key) == key || (key != null && key.equals(k))))
      // 해시값이 같고 키도 같은 경우
      e = p;
    else if (p instanceof TreeNode)
      // 테이블에서 가져온 노드가 TreeNode라면 아이템을 트리에 입력한다
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
      // 그 외의 경우 LinkedList로 관리한다
      for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
          // 새로운 노드를 만들어 LinkedList에 추가한다
          p.next = newNode(hash, key, value, null);

          // 만약 LinkedList 아이템 수가 threshold 이상이면 트리로 만든다
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
        }
        if (e.hash == hash &&
          ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        p = e;
      }
    }
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  ++modCount;
  if (++size > threshold)
    resize();
  afterNodeInsertion(evict);
  return null;
}

public class Key {
  private final int i;

  public Key(int i) {
    this.i = i;
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) {
      return true;
    }
    if (o == null || getClass() != o.getClass()) {
      return false;
    }
    Key key = (Key) o;
    return i == key.i;
  }

  @Override
  public String toString() {
    return "Key:" + i;
  }

  // 여기가 핵심
  @Override
  public int hashCode() {
    return i % 3;   // 0, 1, 2
  }
}

public Node<K, V>[] getTable() {
  return table;
}

public static final class TreeNode<K, V> extends _LinkedHashMap.Entry<K, V> {
  TreeNode<K, V> parent;  // red-black tree links
  public TreeNode<K, V> left;
  public TreeNode<K, V> right;
  TreeNode<K, V> prev;    // needed to unlink next upon deletion

  // ...
}

static void printRecur(Node<Key, Integer> node, int level) {
  if (node instanceof _HashMap.TreeNode) {
    // 트리인 경우
    _HashMap.TreeNode<Key, Integer> tree = (_HashMap.TreeNode<Key, Integer>) node;
    tree.level = level;
    System.out.println(Strings.repeat("  ", level) + "Tree " + ((Node) tree));

    if (tree.left != null) {
      printRecur(tree.left, level + 1);
    }
    if (tree.right != null) {
      printRecur(tree.right, level + 1);
    }
    return;
  } else {
    // 연결 리스트인 경우
    node.level = level;
    System.out.println(Strings.repeat("  ", level) + "Link " + node);
    if (node.getNext() != null) {
      printRecur(node.getNext(), level + 1);
    }
  }
}

@Nested
static class IncrementalInput {
  private _HashMap<Key, Integer> map = new _HashMap<>();

  @BeforeEach
  void prepareTest() {
    map.clear();
    List<Integer> givenList = List.of(
        // 해시값 0 후보
        0, 3, 6, 9, 12, 15, 18, 21, 24,
        // 해시값 1 후보
        1, 4, 7, 10, 13, 16, 19, 22, 25, 28,
        // 해시값 2 후보
        2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38
    );
    for (var i :  givenList) {
      map.put(new Key(i), i);
    }
  }

  @Test
  void it() {
    final Node<Key, Integer>[] nodes = map.getTable();

    for (var node : nodes) {
      if (node == null) {
        continue;
      }
      System.out.println();
      printRecur(node, 0);
    }
  }
}

final TreeNode<K, V> putTreeVal(_HashMap<K, V> map, Node<K, V>[] tab,
                                int key_hash, K given_key, V given_value) {
  Class<?> key_class = null;
  boolean searched = false;
  TreeNode<K, V> root = (parent != null) ? root() : this;

  // 무한 루프를 돌며 given_key / given_value를 집어넣을 곳을 찾는다.
  for (TreeNode<K, V> pointer_node = root; ; ) {
    int direction, pointer_hash;
    K pointer_key;
    if ((pointer_hash = pointer_node.hash) > key_hash)
      // 만약 포인터 노드의 해시값이, 주어진 key의 해시값보다 크다면 방향은 왼쪽
      direction = -1;
    else if (pointer_hash < key_hash)
      // 만약 포인터 노드의 해시값이, 주어진 key의 해시값보다 작다면 방향은 오른쪽
      direction = 1;
    else if ((pointer_key = pointer_node.key) == given_key || (given_key != null && given_key.equals(pointer_key)))
      // 만약 포인터 노드와 주어진 key 가 같다면 중복이다. 삽입하지 않고 그냥 포인터 노드를 리턴한다.
      return pointer_node;
    else if ((key_class == null && (key_class = comparableClassFor(given_key)) == null)
            ||
            (direction = compareComparables(key_class, given_key, pointer_key)) == 0) {
      // 만약 주어진 key 클래스가 Comparable 인터페이스를 구현한다면 key_class를 할당한다.
      // 만약 주어진 key 클래스가 Comparable 구현체가 맞다면 compare 해보고, 결과가 0인지(같은지) 판별한다.
      if (!searched) {
        // 이번 루프에서 삽입할 지점을 찾지 못했다면 이번에 찾는다
        TreeNode<K, V> found_node, child_node;
        searched = true;
        if (
            ((child_node = pointer_node.left) != null && (found_node = child_node.find(key_hash, given_key, key_class)) != null)
            ||
            ((child_node = pointer_node.right) != null && (found_node = child_node.find(key_hash, given_key, key_class)) != null)
        )
          // 왼쪽 또는 오른쪽 중 중복된 key 를 갖는 노드를 찾았다면 삽입하지 않고 리턴한다.
          return found_node;
      }
      // direction이 0,-1 인지 1 인지에 따라 새로운 노드를 왼쪽에 붙일지 오른쪽에 붙일지가 달라진다.
      direction = tieBreakOrder(given_key, pointer_key);
      // ↑ 주목: 같은 해시값을 갖는 노드를 어느 방향에 붙일지 결정한다
    }

    TreeNode<K, V> xp = pointer_node;
    // direction이 0 이하이면 왼쪽에 붙이고, 1 이면 오른쪽에 붙인다.
    if ((pointer_node = (direction <= 0) ? pointer_node.left : pointer_node.right) == null) {
      // 붙일 노드가 null 이라면 새로운 노드를 생성해 key / value를 붙인다.
      Node<K, V> xp_next = xp.next;
      TreeNode<K, V> new_tree_node = map.newTreeNode(key_hash, given_key, given_value, xp_next);
      if (direction <= 0)
        xp.left = new_tree_node;
      else
        xp.right = new_tree_node;
      xp.next = new_tree_node;
      new_tree_node.parent = new_tree_node.prev = xp;
      if (xp_next != null)
        ((TreeNode<K, V>) xp_next).prev = new_tree_node;
      moveRootToFront(tab, balanceInsertion(root, new_tree_node));
      return null;
    }
  }
}

/**
 * Tie-breaking utility for ordering insertions when equal
 * hashCodes and non-comparable. We don't require a total
 * order, just a consistent insertion rule to maintain
 * equivalence across rebalancings. Tie-breaking further than
 * necessary simplifies testing a bit.
 */
static int tieBreakOrder(Object a, Object b) {
  int d;
  if (a == null || b == null ||
      (d = a.getClass().getName().
          compareTo(b.getClass().getName())) == 0) {
    d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
        -1 : 1);
  }
  return d;
}