leetcode【705】设计哈希集合-蒲公英云

leetcode【705】设计哈希集合

电玩女神 2021-10-03 01:48 329阅读 0赞

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

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

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

解题思路：利用LinkedList进行哈希桶的设计，因为LinkedList自带头插方法，在jdk1.7之前都是头插，jdk1.8之后都是进行尾插。然后用valueOf方法进行判断是否含有。

class MyHashSet {
    private Bucket[] buckets;
    private int key_space;
    /** Initialize your data structure here. */
    public MyHashSet() {
        this.key_space = 1024;
        buckets = new Bucket[key_space];
        for(int i = 0;i<key_space;i++)
            buckets[i] = new Bucket();
    }
    public void add(int key) {
        int index = key%key_space;
        buckets[index].insert(key);
    }
    public void remove(int key) {
        int index = key%key_space;
        buckets[index].delete(key);
    }
    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        int index = key%key_space;
        return buckets[index].exist(key);
    }
}
class Bucket{
    private LinkedList<Integer> mybucket;
    public Bucket(){
        mybucket = new LinkedList<>();
    }
    public void insert(int key){
        int index = mybucket.indexOf(key);
        if(index == -1)
            mybucket.addFirst(key);
    }
    public void delete(Integer key){
        mybucket.remove(key);
    }
    public boolean exist(Integer key){
        int index = mybucket.indexOf(key);
        return index!=-1;
    }
}