题目

不使用任何内建的哈希表库设计一个哈希映射

具体地说，你的设计应该包含以下的功能

put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。
get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。
remove(key)：如果映射中存在这个键，删除这个数值对。

示例：

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // 返回 1
hashMap.get(3);            // 返回 -1 (未找到)
hashMap.put(2, 1);         // 更新已有的值
hashMap.get(2);            // 返回 1 
hashMap.remove(2);         // 删除键为2的数据
hashMap.get(2);            // 返回 -1 (未找到)

注意：

所有的值都在 [1, 1000000] 的范围内。
操作的总数目在 [1, 10000] 范围内。
不要使用内建的哈希库。

方案一（切片）

type MyHashMap struct {
    set []bool
    container []int
}

/** Initialize your data structure here. */
func Constructor() MyHashMap {
    return MyHashMap {
        set: make([]bool, 1000001, 1000001),
        container: make([]int, 1000001, 1000001),
    }
}

/** value will always be non-negative. */
func (this *MyHashMap) Put(key int, value int)  {
    this.set[key] = true
    this.container[key] = value
}

/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
func (this *MyHashMap) Get(key int) int {
    in := this.set[key]
    value := this.container[key]
    if in {
        return value
    } else {
        return -1
    }
}

/** Removes the mapping of the specified value key if this map contains a mapping for the key */
func (this *MyHashMap) Remove(key int)  {
    this.set[key] = false
}

因为值可能是0，所以直接使用一个数组来存储 Get 时会有麻烦。

方案二

参考 leetcode 方案，可使用以下方案

type hash struct {
    value int
}

type MyHashMap struct {
    container []*hash
}

/** Initialize your data structure here. */
func Constructor() MyHashMap {
    return MyHashMap {
        container: make([]*hash, 1000001, 1000001),
    }
}

/** value will always be non-negative. */
func (this *MyHashMap) Put(key int, value int)  {
    hash := &hash {
        value: value,
    }
    this.container[key] = hash
}

/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
func (this *MyHashMap) Get(key int) int {
    hash := this.container[key]
    if hash != nil {
        return hash.value
    } else {
        return -1
    }
}

/** Removes the mapping of the specified value key if this map contains a mapping for the key */
func (this *MyHashMap) Remove(key int)  {
    this.container[key] = nil
}

方案三

const NUMBER_OF_BUCKET = 1000

type hash struct {
    key int
    value int
}

type MyHashMap struct {
    bucket [][]*hash
}

/** Initialize your data structure here. */
func Constructor() MyHashMap {
    return MyHashMap {
        bucket: make([][]*hash, NUMBER_OF_BUCKET, NUMBER_OF_BUCKET),
    }
}

func (this *MyHashMap)getBucket(key int) []*hash {
    index := key % NUMBER_OF_BUCKET
    return this.bucket[index]
}

/** value will always be non-negative. */
func (this *MyHashMap) Put(key int, value int)  {
    bucket := this.getBucket(key)
    for _, hash := range bucket {
        if hash != nil && hash.key == key {
            hash.value = value
        }
    }

    _hash := &hash{
        key: key,
        value: value,
    }

    index := key % NUMBER_OF_BUCKET
    this.bucket[index] = append(this.bucket[index], _hash)
}

/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
func (this *MyHashMap) Get(key int) int {
    bucket := this.getBucket(key)
    for _, hash := range bucket {
        if hash != nil && hash.key == key {
            return hash.value
        }
    }

    return -1
}

/** Removes the mapping of the specified value key if this map contains a mapping for the key */
func (this *MyHashMap) Remove(key int)  {
    bucket := this.getBucket(key)
    for i, hash := range bucket {
        if hash != nil && hash.key == key {
            bucket[i] = nil
        }
    }
}