0

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

我正在尝试使用 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 Collection of LinkedList 中的“插入”和“查找”函数的例子吗？我需要一个单独的索引吗？除了 K 和 V。

非常感谢您提前。

4

1 回答 1

0

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

Dictionary 类是任何类的抽象父类，例如 Hashtable，它将键映射到值。每个键和每个值都是一个对象。在任何一个 Dictionary 对象中，每个键最多与一个值相关联。给定一个字典和一个键，可以查找相关的元素。任何非空对象都可以用作键和值。通常，此类的实现应使用 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) { try {

            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");
    }
}

此示例还显示了如何使用 Buckets（在本例中为 LinkedList）来避免碰撞 调用此方法seperate chaining

于 2013-01-22T23:45:08.663 回答