实现

点我查看完整代码 :) 🚀🚀🚀
这里采用的是固定table容量的实现，主要用于感受 hash冲突 对于性能的影响
如果容量是8，put10万次和容量是1008，put10w次的速度不是一个量级的，主要还是链表对于性能的影响

  1. package io.github.chenshun00.data.hash;
  3. import java.util.Objects;
  5. /**
  6.  * 简单hash实现，一个固定数组+链表实现，不进行 <strong>rehash</strong>
  7.  *
  8.  * @author chenshun00@gmail.com
  9.  * @since 2021/9/4 4:49 下午
  10.  */
  11. public class SimpleHashImpl<K, V> implements Hash<K, V> {
  13.     public Node<K, V>[] tables;
  15.     private int size;
  17.     @SuppressWarnings("unchecked")
  18.     public SimpleHashImpl(int capacity) {
  19.         this.tables = new Node[capacity];
  20.     }
  22.     @Override
  23.     public V put(K key, V value) {
  24.         check(key, value);
  25.         final int hash = hash(key);
  27.         final int index = hash & (tables.length - 1);
  28.         Node<K, V> head = tables[index];
  29.         if (head == null) {
  30.             final Node<K, V> kvNode = new Node<>(key, value, null);
  31.             tables[index] = kvNode;
  32.         } else {
  33.             if (head.k.equals(key)) {
  34.                 final V v = head.v;
  35.                 head.v = value;
  36.                 return v;
  37.             }
  38.             while (head.next != null) {
  39.                 head = head.next;
  40.                 final K k = head.k;
  41.                 if (k.equals(key)) {
  42.                     final V v = head.v;
  43.                     head.v = value;
  44.                     return v;
  45.                 }
  46.             }
  47.             head.next = new Node<>(key, value, null);
  48.         }
  49.         incr();
  50.         return null;
  51.     }
  53.     @Override
  54.     public V get(K key) {
  55.         Objects.requireNonNull(key, "key can't be null");
  56.         final int hash = hash(key);
  58.         final int index = hash & (tables.length - 1);
  59.         Node<K, V> head = tables[index];
  60.         if (head == null) {
  61.             return null;
  62.         }
  63.         if (head.k.equals(key)) {
  64.             return head.v;
  65.         }
  66.         head = head.next;
  67.         do {
  68.             if (head.k.equals(key)) {
  69.                 return head.v;
  70.             }
  71.             head = head.next;
  72.         } while (head.next != null);
  73.         return null;
  74.     }
  76.     @Override
  77.     public V remove(K key) {
  78.         Objects.requireNonNull(key, "key can't be null");
  79.         final int hash = hash(key);
  81.         final int index = hash & (tables.length - 1);
  82.         Node<K, V> head = tables[index];
  83.         if (head == null) {
  84.             return null;
  85.         }
  86.         if (head.k.equals(key)) {
  87.             if (head.next == null) {
  88.                 tables[index] = null;
  89.             } else {
  90.                 tables[index] = head.next;
  91.             }
  92.             decr();
  93.             return head.v;
  94.         }
  95.         Node<K, V> leader = head;
  96.         head = head.next;
  97.         do {
  98.             if (head.k.equals(key)) {
  99.                 leader.next = head.next;
  100.                 decr();
  101.                 return head.v;
  102.             }
  103.             leader = head;
  104.             head = head.next;
  105.         } while (head.next != null);
  106.         return null;
  107.     }
  109.     @Override
  110.     public int size() {
  111.         return size;
  112.     }
  114.     private void incr() {
  115.         size++;
  116.     }
  118.     private void decr() {
  119.         size--;
  120.     }
  121. }

测试代码

  1. public class SimpleHashImplTest {
  3.     //可以感受到hash冲突对于put性能的严重影响
  4.     //如果容量是8，put10万次和容量是1008，put10w次的速度不是一个量级的，主要还是链表对于性能的影响
  5.     private final Hash<String, String> simple = new SimpleHashImpl<>(1008);
  7.     @Test
  8.     public void put() {
  9.         String put = simple.put("first", "first");
  10.         Assert.assertNull(put);
  11.         Assert.assertEquals(1, simple.size());
  12.         put = simple.put("first", "reFirst");
  13.         Assert.assertNotNull(put);
  14.         Assert.assertEquals(1, simple.size());
  15.         for (int i = 0; i < 100000; i++) {
  16.             simple.put("first" + i, "first" + i);
  17.         }
  18.         Assert.assertEquals(100001, simple.size());
  19.         Assert.assertEquals("first88", simple.get("first88"));
  21.         final String first88 = simple.remove("first88");
  22.         Assert.assertEquals("first88", first88);
  23.         Assert.assertEquals(100000, simple.size());
  24.     }
  25. }