来自字典集合的链接列表

Question

我是整个"数据结构"的新手。

我正在尝试使用LinkedList（来自Java集合）实现字典。我截断了过去某人的一个例子。

[条目.java]

public class Entry<K, V> {
    K key;
    V value;
    public Entry(K key, V value) {
        this.key = key;
        this.value = value;
    }
    public K key() {
        return key;
    }
    public V value() {
        return value;
    }
}

[字典.java]

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class Dictionary<K, V> {
    private List<Entry<K, V>> set;
    public Dictionary() {
        this.set = new LinkedList<Entry<K, V>>();
    }
    public Entry<K, V> find(K key) {
        // for all entries in set...
        //   check if key mathches
        //     - if it does than return it
        // else
        return null;
    }

    /**
     * insert(k, o): inserts and returns the entry (k, o)
     */
    public Entry<K, V> insert(K key, V value) {
        // obvious
        return null;
    }
    public int size() {
        return set.size();
    }
    public boolean isEmpty() {
        return size() == 0;
    }
}

你能给我看一个如何使用 Java 集合中的"插入"和"查找"函数的示例吗？我需要单独的索引吗？除了 K 和 V。

提前非常感谢你。

Answer 1

地图界面就是您要查找的。 根据Javadocs：

字典类是任何类的抽象父级，例如 哈希表，将键映射到值。每个键和每个值都是一个 对象。在任何一个字典对象中，每个键都与 最多一个值。给定一个字典和一个键，关联的元素 可以查找。任何非空对象都可以用作键和 价值。通常，实现应使用 equals 方法 来决定两个键是否相同。

注意：此类是 过时。新的实现应该实现 Map 接口， 而不是扩展此类。

正如Javadocs声明哈希映射包含键值对一样，以下是您实现此类的方式：

    package hashmap;
import java.util.*;
public class HashMap<K,V> implements Map<K,V> {
    private final int TABLESIZE = 101;
    private LinkedList<Node<K, V>>[] list;
    @SuppressWarnings("unchecked")
    public HashMap() {
        // Creates a hash table with a table size of TABLESIZE  
        list = new LinkedList[TABLESIZE];
    }
    // Returns the Hasindex of a key
    private int getHashIndex(Object key) {
        String hashCode = key.toString();
        int i = Integer.parseInt(hashCode.substring(hashCode.length() - 4));
        return i % TABLESIZE;
    }

首先找到存储桶，然后迭代每个存储桶的 get 方法 public V get（Object key） { 尝试 {

            LinkedList<Node<K,V>> bucket = list[getHashIndex(key)]; 
            Iterator<Node<K,V>> itr = bucket.iterator();
            while (itr.hasNext()) {
                Node<K,V> node = itr.next();
                if (node.getKey().equals(key)) {
                    return node.getValue();
                }
            }
        }
        // if there is no bucket return null
        catch (NullPointerException e) {
            return null;
        }
        return null;
    }
       //add method
    public V put(K key, V value) {  
        // Hvis der ikke er en spand i forvejen tilføjes en ny
        if (list[getHashIndex(key)] == null) {
            list[getHashIndex(key)] = new LinkedList<Node<K,V>>();
        }
        LinkedList<Node<K,V>> bucket = list[getHashIndex(key)]; 
        Iterator<Node<K,V>> itr = bucket.iterator();
        V prevouis = null;
        while (itr.hasNext()) {
            Node<K,V> node = itr.next();
            if (node.getKey().equals(key)) {
                prevouis = node.getValue();
                bucket.remove(node);
                break;
            }
        }
        bucket.addLast(new Node<K,V>(key, value));

        return prevouis;
    }
    // remove method
    public V remove(Object key) {
        // Itererer igennem spanden for at finde og slette den korrekte nøgle       
        LinkedList<Node<K,V>> bucket = list[getHashIndex(key)]; 
        Iterator<Node<K,V>> itr = bucket.iterator();
        V value = null;
        while (itr.hasNext()) {
            Node<K,V> node = itr.next();
            if (node.getKey().equals(key)) {
                value = node.getValue();
                bucket.remove(node);
                break;
            }
        }

        if (bucket.isEmpty()) {
            list[getHashIndex(key)] = null;
        }

        return value;
    }
    @Override
    public void clear() {
        // TODO Auto-generated method stub
    }
    @Override
    public boolean containsKey(Object key) {
        // TODO Auto-generated method stub
        return false;
    }
    @Override
    public boolean containsValue(Object value) {
        // TODO Auto-generated method stub
        return false;
    }
    @Override
    public Set<java.util.Map.Entry<K, V>> entrySet() {
        // TODO Auto-generated method stub
        return null;
    }
    @Override
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return false;
    }
    @Override
    public Set<K> keySet() {
        // TODO Auto-generated method stub
        return null;
    }
    @Override
    public void putAll(Map<? extends K, ? extends V> m) {
        // TODO Auto-generated method stub
    }
    @Override
    public int size() {
        // TODO Auto-generated method stub
        return 0;
    }
    @Override
    public Collection<V> values() {
        // TODO Auto-generated method stub
        return null;
    }

    public void printHashTable() {
        System.out.println("HashTable:");
        int nodeCount = 0;
        for (int i = 0; i < list.length; i++) {
            LinkedList<Node<K,V>> bucket = list[i];
            if (bucket != null) {
                nodeCount += bucket.size();
                System.out.println("Index " + i + ": " + bucket);
            }
        }
        System.out.println("Total nodes: " + nodeCount + "n");
    }
}

此示例还显示了如何使用避免共患 与使用存储桶（在本例中为 LinkedList）一起使用此方法称为seperate chaining