LeetCode 706：Design HashMap 实现一个简单的哈希映射

题目描述：

Design a HashMap without using any built-in hash table libraries.

To be specific, your design should include these functions:

• put(key, value): Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
• get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

Example:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // returns 1
hashMap.get(3);            // returns -1 (not found)
hashMap.put(2, 1);          // update the existing value
hashMap.get(2);            // returns 1 
hashMap.remove(2);          // remove the mapping for 2
hashMap.get(2);            // returns -1 (not found)

Note:

All keys and values will be in the range of [0, 1000000].
The number of operations will be in the range of [1, 10000].
Please do not use the built-in HashMap library.

题解

题目大意：

题目意思其实很简单，就是设计一个HashMap包含题目给出的几个函数，不能使用内置的HashMap库。

实现：

正好最近在用python尝试构建hash表，顺道把这道题也一起解了。
用Python实现的一个简单的Hash表，采用hash函数是取余，用线性探测解决冲突问题。

class HashTable:

    # 初始化
    def __init__(self, size):
        self.elem = [None for i in range(size)]                # 创建一个列表保存哈希元素,值全为None
        self.count = size                                      # 最大表长

    # 散列函数
    def hash(self, key):
        return key % self.count                                # 散列函数采用除留余数法

    # 插入
    def insert_hash(self, key):
        print(key)
        address = self.hash(key)                               # 计算散列地址
        print(address)
        while self.elem[address] != None:                      # 发生冲突
            address = (address + 1) % self.count               # 线性探测解决冲突
        print(address)
        self.elem[address] = key                               # 没有冲突
        print(self.elem)

    # 查找
    def search_hash(self, key):
        star = address = self.hash(key)                               # 查找关键字
        while self.elem[address] != key:
            address = (address + 1) % self.count
            if not self.elem[address] or address == star:             # 说明没找到或者循环到了开始的位置
                return False
        return True

if __name__ == '__main__':
    list_a = [0, 12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34]
    hash_table = HashTable(len(list_a))
    for i in list_a:
        hash_table.insert_hash(i)

    for i in hash_table.elem:
        if i:
            print((i, hash_table.elem.index(i)))

    print(hash_table.search_hash(15))
    print(hash_table.search_hash(33))

针对这道题，也可以采用取余作为hash函数，采用“拉链法”处理冲突，将相同hash值的对象组织成一个链表放在hash值对应的位置；具体原理和Java中的HashMap实现的原理类似。具体代码如下：

class MyHashMap:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.buckets = 1000                       # 键值块，哈希桶
        self.itemsPerBuckect = 1001               # 产生冲突的“拉链”块
        self.hashmap = [[] for _ in range(self.buckets)]        # _表示临时变量，仅用一次，后面无需用到

    # 散列函数
    def hash(self, key):
        return key % self.buckets                 # 取余

    # 处理冲突的函数
    def pos(self, key):
        return key // self.buckets                # 向下取整，返回商的整数部分

    def put(self, key, value):
        """
         value will always be positive.
         :type key: int
         :type value: int
         :rtype: void
        """
        hashkey = self.hash(key)
        if not self.hashmap[hashkey]:                 # 没有产生冲突，直接填入buckets中
            self.hashmap[hashkey] = [None] * self.itemsPerBuckect
        self.hashmap[hashkey][self.pos(key)] = value

    def get(self, key):
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
        :type key: int
        :rtype: int
        """
        hashkey = self.hash(key)
        if(not self.hashmap[hashkey]) or self.hashmap[hashkey][self.pos(key)] == None:      # 没有找到这个值
            return -1
        else:
            return self.hashmap[hashkey][self.pos(key)]

    def remove(self, key):
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key
        :type key: int
        :rtype: void
        """
        hashkey = self.hash(key)
        if self.hashmap[hashkey]:
            self.hashmap[hashkey][self.pos(key)] = None


if __name__ == "__main__":
    hashmap = MyHashMap()
    hashmap.put(1, 1)
    hashmap.put(2, 2)
    hashmap.get(1)
    hashmap.get(3)
    hashmap.put(2, 1)
    hashmap.get(2)
    hashmap.remove(2)
    hashmap.get(2)

python极简版本：

class MyHashMap:

    def __init__(self):
        self.arr = [-1] * 1000001

    def put(self, key, value):
        self.arr[key] = value

    def get(self, key):
        return self.arr[key]

    def remove(self, key):
        self.arr[key] = -1

c++实现版本，直接用vector容器模拟，没有考虑冲突情况。

class MyHashMap {
public:
    /** Initialize your data structure here. */
    vector<int> hashMap;
    MyHashMap() {
        
    }
    
    /** value will always be non-negative. */
    void put(int key, int value) {
        if(key >= hashMap.size()){
            for(int i = hashMap.size(); i <= key; i++){
                hashMap.push_back(-1);
            }
        }
        hashMap[key] = value;
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        if(key >= hashMap.size()) 
            return -1;
        return hashMap[key];
        
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        if(key >= hashMap.size()) 
            return;
        hashMap[key] = -1;
    }
};