golang刷leetcode 经典（5)设计哈希集合

golangLeetcode

发布于 2022-08-02 17:32:28

2560

发布于 2022-08-02 17:32:28

文章被收录于专栏：golang算法架构leetcode技术php

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

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

add(value)：向哈希集合中插入一个值。

contains(value) ：返回哈希集合中是否存在这个值。

remove(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

示例:

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

注意：

所有的值都在 [0, 1000000]的范围内。

操作的总数目在[1, 10000]范围内。

不要使用内建的哈希集合库。

解题思路：

1，本题考察对hashset 的理解

2，使用拉链法

3，设计简单的hash函数，取模

hashset 和hashmap 区别：

HashSet：

HashSet实现了Set接口，它不允许集合中出现重复元素。当我们提到HashSet时，第一件事就是在将对象存储在

HashSet之前，要确保重写hashCode（）方法和equals（）方法，这样才能比较对象的值是否相等，确保集合中没有

HashMap：

HashMap实现了Map接口，Map接口对键值对进行映射。Map中不允许出现重复的键（Key）。Map接口有两个基本的实现

TreeMap和HashMap。TreeMap保存了对象的排列次序，而HashMap不能。HashMap可以有空的键值对（Key（null）-Value（null））

总结一句话，hash set node节点里存储的是key，hash map node节点存储的是key value pair

代码

type MyHashSet struct {
    data []*Node
    len int
}

type Node struct{
    key int
    next  *Node
}

/** Initialize your data structure here. */
func Constructor() MyHashSet {
    return MyHashSet{
        data:make([]*Node,10001),
        len:10001,
    }
}


func (this *MyHashSet) Add(key int)  {
    data:=this.data[key%this.len]
    if data==nil{
        this.data[key%this.len]=&Node{
           key:key,
        }
    }else{
            if data.key==key{
                return
            }
        for data.next!=nil{
            data=data.next
            if data.key==key{
                return
            }
        }
        data.next=&Node{
            key:key,
        }
    }
    //this.Print()
}

func (this *MyHashSet)Print(){
   fmt.Println("----",this.len,":")
   for i:=0;i<len(this.data);i++{
       d:=this.data[i]
       if d!=nil{
           fmt.Println(this.data[i].key)
           for d.next!=nil{
               d=d.next
                fmt.Println(d.key)
           }     
       }
   }
   fmt.Println(":------")
}

func (this *MyHashSet) Remove(key int)  {
    data:=this.data[key%this.len]
    if data==nil{
        return
    }
    if data.key==key{
        this.data[key%this.len]=data.next
        //this.Print()
        return
    }
    for data.next!=nil{
        if data.next.key!=key{
            data=data.next
        }else{
            data.next=data.next.next
        }
    }
}


/** Returns true if this set contains the specified element */
func (this *MyHashSet) Contains(key int) bool {
    data:=this.data[key%this.len]
    if data==nil{
        return false
    }
    for data.next!=nil{
        if data.key==key{
            return true
        }
        data=data.next
    }
    return data.key==key
}


/**
 * Your MyHashSet object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(key);
 * obj.Remove(key);
 * param_3 := obj.Contains(key);
 */

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-12-23，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法