模拟实现HashMap

妖狐艹你老母 2023-01-13 04:19 88阅读 0赞

### 模拟实现HashMap ###

*  模拟实现HashMap
 *   *  注意事项

关于Set和Map区别：

见链接： [Set和Map][Set_Map]

关于HashTable  
见链接： [哈希表][Link 1]

# 模拟实现HashMap #

Node：

public class Node { 
        public String key;
    
        public Integer value;
        public Node next;
    
        public Node(String key, Integer value) { 
            this.key = key;
            this.value = value;
        }
    }

模拟实现：

public class MyHashMap { 
        private Node[] array;
        private int size;
    
        public MyHashMap() { 
            array = new Node[16];
            size = 0;
        }
    
        //计算出index
        private int indexOf(String key) { 
            int hash = key.hashCode();
            int h = hash ^ (hash >> 16);
            //前提：array.length.一定2的多少次方，16/32/64/128.
    
            return h & (array.length - 1);
        }
    
        //get
        public Integer get(String key) { 
            int index = indexOf(key);
            Node cur = array[index];
            while (cur != null) { 
                if (key.equals(cur.key)) { 
                    return cur.value;
                }
                cur = cur.next;
            }
            return null;
        }
    
        //getOrDefault
        public Integer getOrDefault(String key, Integer value) { 
            int index = indexOf(key);
            Node cur = array[index];
            while (cur != null) { 
                if (key.equals(cur.key)) { 
                    return cur.value;
                }
                cur = cur.next;
            }
            return value;
        }
    
        //put
        public Integer put(String key, Integer value) { 
            int index = indexOf(key);
            Node cur = array[index];
            while (cur != null) { 
                if (key.equals(cur.key)) { 
                    Integer oldValue = cur.value;
                    cur.value = value;
                    return oldValue;
                }
                cur = cur.next;
            }
    
            Node node = new Node(key, value);
            node.next = array[index];
            array[index] = node;
            size++;
    
            //考虑是否扩容问题
            if ((double) size / array.length > 0.5) { 
                grow();
            }
            return null;
        }
    
        private void grow() { 
            Node[] newArray = new Node[array.length * 2];
    
            for (Node head : array) { 
                Node cur = head;
                while (cur != null) { 
                    int index = indexOf(cur.key) % newArray.length;
                    Node next = cur.next;
    
                    cur.next = newArray[index];
                    newArray[index] = cur;
    
                    cur = next;
                }
            }
            array = newArray;
        }
    
    }

注意：  
没有将所有的方法都实现，但是大致思路都一致；  
hashSet和hashMap差不多，（hashSet的底层是hashMap实现）  
另外：当key的值不是Int类型的时候，我们需要利用 hashCode(),将其转换为int型计算其下标。

## 注意事项 ##

Java中实现了HashSet、HashMap、和LinkedHashSet和 LinkedHashMap  
当我们使用Java中自带实现的HashMap和HashSet的时候一定要注意正确的使用hashCode()，另外还要正确的重写hashCode和equals方法。

LinkedHashSet和 LinkedHashMap，是链表 + 哈希表 组成  
维护 element/key的有序，是按照插入顺序维护的。

[Set_Map]: https://blog.csdn.net/weixin_52142731/article/details/115696433
[Link 1]: https://blog.csdn.net/weixin_52142731/article/details/115733616