如何在 Java 中实现集合数据结构？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/29137250/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to implement a Set Data Structure in Java?
提问by ArsenalRocks
I have always wondered how would you implement a Set in Java. Can we implement it just like we implement a HashMap using a LinkedList and an object(Cell) which holds a Key and Value? How would you handle the uniqueness part?
我一直想知道如何在 Java 中实现 Set。我们能否像使用 LinkedList 和一个包含键和值的对象（Cell）来实现 HashMap 一样实现它？你将如何处理独特性部分？
采纳答案by rns
回答by Paul
Basically, a Set is just a Map that only holds keys. So you should inform yourself about mappingalgorithms. Note: the HashSet for example is actually just an adapter for the HashMap. the add-method of HashSet simply uses HashMap.put(value , SomeDummyValue).
基本上，一个 Set 只是一个只保存键的 Map。因此，您应该了解映射算法。注意：例如 HashSet 实际上只是 HashMap 的适配器。HashSet 的添加方法仅使用 HashMap.put(value , SomeDummyValue)。
回答by bitsabhi
Below is a code snippet to explain above answers
以下是解释上述答案的代码片段
public HashSet() { map = new HashMap<>(); }
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
// Since PRESENT is a constant, for all keys we have same value in backup HashMap called map.
public Iterator<E> iterator() {
return map.keySet().iterator();
}
回答by Vicky Raj
class HashSetBasicImpl<K> {
static class Entry<K> {
private K key;
private Entry<K> next;
Entry(K key) {
key = key;
next = null;
}
}
private Entry<K>[] entries;
public HashSetBasicImpl() {
// fixed size
map =new Entry[100];
}
public boolean contains(K key) {
int idx = key.hashCode();
Entry<K> start = entries[idx];
while(start != null) {
if(start.key == key) {
return true;
}
start = start.next;
}
return false;
}
public boolean add(K key) {
Entry<K> entry = new Entry(key);
int idx = key.hashCode();
// check if entry exists
if(contains(key)) {
return false;
}
// add as first entry
start = entries[idx];
if(start == null) {
entries[idx]= new Entry(key);
return true;
}
// add as nth entry
Entry prev = null;
while(start != null) {
prev = start;
start = start.next;
}
prev.next = new Entry(key);
return true;
}
}
