【LeetCode】 706. （JAVA）设计哈希集合链表实现

不念不忘少年蓝@ 2021-06-10 20:37 343阅读 0赞

总体来讲，这个效果不是很优秀，而且有问题，因为size要设置的很大就可以，设置小了就出错，还没来得及找出来原因，先贴出来吧

## 题目： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## 解决： ##

思路：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]

1.  使用链表实现的哈希集合，其实总体来说把，这么做不太好，遍历会很麻烦，必须要从头到尾，这样就会导致时间复杂度一直都是n级别的
2.  如果len设置的小就不通过，还没搞清楚原因
3.  整体使用的还是内部的链表结构实现的
4.  我封装了一个Node，用来保存每个key-val，如图，每个key下是一个链表，每个链表的节点里面是一个Node

class MyHashMap { 
    
        LinkedList<Node>[] linkedLists;
        final int len = 100000;
    
        public MyHashMap() { 
            linkedLists = new LinkedList[len];
        }
    
        public void put(int key, int value) { 
            Node node = new Node(key, value);
            key %= len;
    
            if (linkedLists[key] == null) linkedLists[key] = new LinkedList<Node>();
            LinkedList linkedList = linkedLists[key];
    
            for (Object o : linkedList) { 
                Node n = (Node) o;
                if (n.getKey() == key) { 
                    linkedList.remove(o);
                }
            }
            linkedList.add(node);
        }
    
        public int get(int key) { 
            LinkedList linkedList = linkedLists[key % len];
            if (linkedList == null) return -1;
            for (Object o : linkedList) { 
                Node node = (Node) o;
                if (node.getKey() == key) return node.getVal();
            }
            return -1;
        }
    
        public void remove(int key) { 
            LinkedList linkedList = linkedLists[key % len];
            if (linkedList == null) return;
            for (Object o : linkedList) { 
                Node node = (Node) o;
                if (node.getKey() == key) { 
                    linkedList.remove(o);
                    return;
                }
            }
        }
    }
    
    class Node { 
        private int key;
        private int val;
    
        public Node(int key, int val) { 
            this.key = key;
            this.val = val;
        }
    
        public int getKey() { 
            return key;
        }
    
        public int getVal() { 
            return val;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/04a94cc7208e4d19b869b9bff88d9725.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]: /images/20210529/09608f8866e54927b620bb48a37030bd.png