2024.4.14力扣每日一题——设计哈希集合

题目来源

力扣每日一题；题序：705

我的题解

方法一 链表数组

由于给定限制次数为10000，所以构造一个长度为10001的链表数组。对于add操作先看数组对应的位置是否为null或者为空，若是则直接加入，否则遍历整个链表看是否有与加入的值相同的元素。对于remove操作，先看数组对应的位置是否为null或者为空，若是则直接退出，否则遍历整个链表看是否有与加入的值相同的元素，若相同则删除对应的链表节点。对于contains操作，先看数组对应的位置是否为null或者为空，若是则直接返回false，否则遍历整个链表看是否有与加入的值相同的元素，若有直接返回true，否则返回false。
对于哈希函数的设计：取key对应的哈希值mod 10000
哈希冲突的解决：使用链地址法解决

class MyHashSet {class LinkedList{int val;LinkedList next;public LinkedList(){}public LinkedList(int v){val=v;}public int size(){LinkedList root=this;int sz=0;while(root!=null){sz++;root=root.next;}return sz;}}private LinkedList[] keys;int n=10001;public MyHashSet() {keys=new LinkedList[n];// Arrays.fill(keys,new LinkedList());}public void add(int key) {int index=myHash(key);// 节点为空if(keys[index]==null){keys[index]=new LinkedList(key);// 还未有元素}else if(keys[index].size()==0){keys[index].val=key;//已经有元素}else{LinkedList root=keys[index];if (root.val==key)return ;while(root.next!=null&&root.next.val!=key){root=root.next;}if(root.next==null)root.next=new LinkedList(key);}}public void remove(int key) {int index=myHash(key);// 节点为空 || 还未有元素if(keys[index]==null||keys[index].size()==0)return ;//已经有元素else{LinkedList root=keys[index];if(root.val==key){keys[index]=root.next;}else{while(root.next!=null&&root.next.val!=key){root=root.next;}if(root.next!=null)root.next=root.next.next;}}}public boolean contains(int key) {int index=myHash(key);// 节点为空 || 还未有元素if(keys[index]==null||keys[index].size()==0)return false;//已经有元素else{LinkedList root=keys[index];while(root!=null){if(root.val==key)return true;root=root.next;}return false;}}public int myHash(int key){int iHash=Integer.hashCode(key);return iHash%(n-1);}@Overridepublic String toString() {return Arrays.toString(keys);}
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~