Design HashSet
2024-09-04 18:25:17
Design a HashSet without using any built-in hash table libraries.
To be specific, your design should include these functions:
add(value): Insert a value into the HashSet.contains(value): Return whether the value exists in the HashSet or not.remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.
Example:
MyHashSet hashSet = new MyHashSet();
hashSet.add(1);
hashSet.add(2);
hashSet.contains(1); // returns true
hashSet.contains(3); // returns false (not found)
hashSet.add(2);
hashSet.contains(2); // returns true
hashSet.remove(2);
hashSet.contains(2); // returns false (already removed)
class MyHashSet {
final ListNode[] nodes = new ListNode[];
/** Initialize your data structure here. */
public MyHashSet() {
}
public void add(int key) {
int i = idx(key);
ListNode first = nodes[i];
if (first == null) {
nodes[i] = new ListNode(key);
} else if (!exists(first, key)) {
ListNode newNode = new ListNode(key);
newNode.next = nodes[i];
nodes[i] = newNode;
}
}
public void remove(int key) {
int i = idx(key);
if (nodes[i] == null) {
return;
}
ListNode current = nodes[i];
ListNode previous = null;
while (current != null) {
if (current.key == key) {
if (previous != null) {
previous.next = current.next;
} else {
nodes[i] = current.next;
}
break;
} else {
previous = current;
current = current.next;
}
}
}
/** Returns true if this set contains the specified element */
public boolean contains(int key) {
int i = idx(key);
ListNode first = nodes[i];
if (first == null) {
return false;
}
return exists(first, key);
}
int idx(int key) {
return key % nodes.length;
}
private boolean exists(ListNode node, int key) {
ListNode current = node;
while (current != null) {
if (current.key == key) {
return true;
}
current = current.next;
}
return false;
}
}
class ListNode {
int key;
ListNode next;
ListNode(int key) {
this.key = key;
}
}
最新文章
- 大数据实践-数据同步篇tungsten-relicator（mysql->mongo）
- 【BZOJ 3642】Phi的反函数
- 微信分享接口SDK简介使用
- mina2线程详解
- 关于Go，你可能不注意的7件事(转的)
- 【转】android程序编译过程
- 出现 could not open jvm.cfg 的解决办法
- AMQ学习笔记 - 15. 实践方案：基于ActiveMQ的统一日志服务
- C#中 ？ 和？？ 的用法
- Objective-C基础笔记一
- hive 中的Sort By、 Order By、Cluster By、Distribute By 区别
- Android零碎知识点总结
- Using CrunchBase API
- Jquery操作Table
- Java 网络 IO 模型
- Hadoop之Secondary NameNode
- Doctype知识点总结
- 支付宝沙箱测试-ALI40247
- linux-git
- Lavarel Route::resource