leetcode【706】设计哈希映射

淩亂°似流年 2021-10-03 01:50 204阅读 0赞

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

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

put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。  
get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。  
remove(key)：如果映射中存在这个键，删除这个数值对。

解题思路：设计键值对类似于利用C++的make\_pair用法，创建pair对象，然后使用LinkedList内置函数的一些用法就可以实现了。

我在之前错误两次的情况是这里用的Intrger对象，而不是int，我用的==就出现问题了。

class Pair<U,V>{
        public U first;
        public V second;
        public Pair(U first,V second){
            this.first = first;
            this.second = second;
        }
    }
    class Bucket{
        private List<Pair<Integer,Integer>> bucket;
        public Bucket(){
            this.bucket = new LinkedList<>();
        }
        public Integer get(Integer key){
            for(Pair<Integer,Integer> pair:bucket){
                if(pair.first.equals(key) )
                    return pair.second;
            }
            return -1;
        }
        public void update(Integer key,Integer value){
            boolean found = false;
            for(Pair<Integer,Integer> pair:bucket){
                if(pair.first.equals(key)) {
                    pair.second = value;
                    found = true;
                }
            }
            if(!found)
                this.bucket.add(new Pair<Integer,Integer>(key,value));
        }
        public void remove(Integer key){
            for(Pair<Integer,Integer> pair:this.bucket){
                if(pair.first.equals(key)){
                    bucket.remove(pair);
                    break;
                }
            }
        }
    }
    class MyHashMap{
        private int ket_space;
        private List<Bucket> hash_table;
    
        public MyHashMap(){
            this.ket_space = 10000;
            this.hash_table = new ArrayList<>();
            for(int i = 0;i<ket_space;i++)
                this.hash_table.add(new Bucket());
        }
        public void put(int key,int value){
            int hash_key = key%ket_space;
            this.hash_table.get(hash_key).update(key,value);
        }
        public int get(int key){
            int hash_key = key%ket_space;
            return this.hash_table.get(hash_key).get(key);
        }
        public void remove(int key){
            int hash_key = key%ket_space;
            this.hash_table.get(hash_key).remove(key);
        }
    }