leetcode【705】设计哈希集合

电玩女神 2021-10-03 01:48 178阅读 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;
        }
    }