706. 设计哈希映射

image.png

题解

  1. class MyHashMap {
  2.     // 桶的大小
  3.     private int hashKeySpace;
  4.     // 桶
  5.     private List<MyBucket<Integer, Integer>> hashTable;
  7.     public MyHashMap() {
  8.         // 初使化桶的大小
  9.         this.hashKeySpace = 2048;
  10.         // 初使化桶
  11.         this.hashTable = new ArrayList<>();
  12.         for (int i = 0; i < this.hashKeySpace; i++) {
  13.             this.hashTable.add(new MyBucket<>());
  14.         }
  15.     }
  17.     public void put(int key, int value) {
  18.         // 获取桶内的链表，操作链表
  19.         MyBucket bucket = getBucketByKey(key);
  20.         bucket.update(new MyEntry<Integer, Integer>(key, value));
  21.     }
  23.     public int get(int key) {
  24.         // 获取桶内的链表，再从链表中获取
  25.         MyBucket bucket = getBucketByKey(key);
  26.         MyEntry entry = bucket.get(key);
  27.         if (entry != null) {
  28.             return (int) entry.getValue();
  29.         }
  30.         return -1;
  31.     }
  33.     public void remove(int key) {
  34.         // 获取桶内的链表，再从链表中删除节点
  35.         MyBucket bucket = getBucketByKey(key);
  36.         bucket.remove(key);
  37.     }
  39.     /**
  40.      * 获取桶内的链表
  41.      * @param key
  42.      * @return
  43.      */
  44.     private MyBucket getBucketByKey(int key) {
  45.         int hash = key % hashKeySpace;
  46.         return hashTable.get(hash);
  47.     }
  48. }
  50. // 节点结构
  51. class MyEntry<K, V> {
  52.     final private K key;
  53.     private V value;
  55.     public MyEntry(K key, V value) {
  56.         this.key = key;
  57.         this.value = value;
  58.     }
  60.     public K getKey() {
  61.         return key;
  62.     }
  64.     public V getValue() {
  65.         return value;
  66.     }
  68.     public void setValue(V value) {
  69.         this.value = value;
  70.     }
  71. }
  73. // 桶里面的链表结构
  74. class MyBucket<K, V> {
  76.     // 链表
  77.     List<MyEntry<K, V>> linklist;
  79.     public MyBucket() {
  80.         linklist = new LinkedList<>();
  81.     }
  83.     /**
  84.      * 为 map 的 put 提供服务，有可能是新增节点，也有可能是更新节点
  85.      * @param entry 要放入链表的节点
  86.      */
  87.     public void update(MyEntry<K, V> entry) {
  88.         // 标记是否是更新节点
  89.         boolean exists = false;
  90.         for (MyEntry<K, V> entryItem : linklist) {
  91.             // 根据 key 判断节点是否已存在，如果存在则更新
  92.             if (entry.getKey().equals(entryItem.getKey())) {
  93.                 entryItem.setValue(entry.getValue());
  94.                 exists = true;
  95.             }
  96.         }
  97.         // 如果 key 不存在，新增节点
  98.         if (!exists) linklist.add(entry);
  99.     }
  101.     /**
  102.      * 根据 key 获取节点
  103.      * @param key
  104.      * @return 如果不存在返回 null
  105.      */
  106.     public MyEntry<K, V> get(int key) {
  107.         for (MyEntry<K, V> entry : linklist) {
  108.             if (entry.getKey().equals(key)) {
  109.                 return entry;
  110.             }
  111.         }
  112.         return null;
  113.     }
  115.     /**
  116.      * 根据 key 删除节点
  117.      * @param key
  118.      */
  119.     public void remove(int key) {
  120.         linklist.removeIf(entry -> entry.getKey().equals(key));
  121.     }
  122. }