题目

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

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

  • add(value)：向哈希集合中插入一个值。
  • contains(value)：返回哈希集合中是否存在这个值。
  • remove(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

示例:

  1. MyHashSet hashSet = new MyHashSet();
  2. hashSet.add(1);         
  3. hashSet.add(2);         
  4. hashSet.contains(1);    // 返回 true
  5. hashSet.contains(3);    // 返回 false (未找到)
  6. hashSet.add(2);          
  7. hashSet.contains(2);    // 返回 true
  8. hashSet.remove(2);          
  9. hashSet.contains(2);    // 返回  false (已经被删除)

注意：

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

方案一（使用内建map）

type MyHashSet struct {
    m map[int]int
}

/** Initialize your data structure here. */
func Constructor() MyHashSet {
    return MyHashSet{
        m: make(map[int]int),
    }
}

func (this *MyHashSet) Add(key int)  {
    this.m[key] = 0
}

func (this *MyHashSet) Remove(key int)  {
    delete(this.m, key)
}

/** Returns true if this set contains the specified element */
func (this *MyHashSet) Contains(key int) bool {
    _, ok := this.m[key]
    return ok
}

方案二（切片）

type MyHashSet struct {
    container []int
}


/** Initialize your data structure here. */
func Constructor() MyHashSet {
    m := MyHashSet{
        container: make([]int, 1000000),
    }
    // 因为切片初始化的值为0，所以对 index == 0 做预处理
    m.container[0] = -1
    return m
}

func (this *MyHashSet) getIndex(key int) int {
    return key % len(this.container)
}


func (this *MyHashSet) Add(key int)  {
    index := this.getIndex(key)
    this.container[index] = key
}


func (this *MyHashSet) Remove(key int)  {
    index := this.getIndex(key)
    this.container[index] = 0
}


/** Returns true if this set contains the specified element */
func (this *MyHashSet) Contains(key int) bool {
    index := this.getIndex(key)
    value := this.container[index]
    if index == 0 {
        return value != -1
    }
    return value != 0
}
  • 使用 key % 1000000 作为哈希函数；由于go语言初始化值为0，所以对 index == 0 的位置做特殊处理

方案三（切片二）

type MyHashSet struct {
    set []bool
}


/** Initialize your data structure here. */
func Constructor() MyHashSet {
    var s MyHashSet 
    s.set = make([]bool, 100001, 100001)
    return s
}


func (this *MyHashSet) Add(key int)  {
    this.set[key] = true
}


func (this *MyHashSet) Remove(key int)  {
    this.set[key] = false
}


/** Returns true if this set contains the specified element */
func (this *MyHashSet) Contains(key int) bool {
    return this.set[key]
}