LeetCode Notes_#705_设计哈希集合

LeetCode

Contents

• • 题目
  • 思路分析
  • 解答
    • 复杂度分析

题目

思路分析

其实很简单，但是函数比较多，看起来有些麻烦，需要提前设计好各个函数的返回值，参数等，互相配合使用。
核心思路：
将数据根据散列函数（或者叫做哈希函数），存储到不同的“桶”当中，做任何操作的时候，先找到对应的桶（相当于缩小范围），然后在桶里进行操作。

解答

class MyHashSet {
    private Bucket[] bucketArray;
    private int bucketNum;

    /** Initialize your data structure here. */
    public MyHashSet() {
        bucketNum = 769;
        bucketArray = new Bucket[bucketNum];
        for(int i = 0;i <= bucketNum - 1;i++){
            bucketArray[i] = new Bucket();
        }
    }

    private int hash(int key){
        return key % bucketNum;
    }
    
    public void add(int key) {
        int bucketIndex = hash(key);
        bucketArray[bucketIndex].bucket_add(key);
    }
    
    public void remove(int key) {
        int bucketIndex = hash(key);
        bucketArray[bucketIndex].bucket_remove(key);
    }
    
    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        int bucketIndex = hash(key);
        return bucketArray[bucketIndex].bucket_contains(key);
    }
}

class Bucket{
    private LinkedList<Integer> bucket;

    public Bucket(){
        bucket = new LinkedList<>();
    }

    //方法设置为public是因为要被MyHashSet类所调用
    public void bucket_add(int key){
        //如果桶里没有相应的key,那么就将其插入到桶里；如果已经包含了key,就不插入
        if(!bucket_contains(key)) bucket.addFirst(key);
    }

    public void bucket_remove(int key){
        int key_index = bucket.indexOf(key);
        if(key_index != -1) bucket.remove(key_index);
    }

    public boolean bucket_contains(int key){
        int index = bucket.indexOf(key);
        return index != -1;
    }
}

复杂度分析

时间复杂度：O(N/K),N是所有键值对的数量，K是桶的数量
空间复杂度：O(K+M),K是桶的数量，M是已经插入的键值对的数量