0

私は「データ構造」全体に不慣れです。

LinkedList(From Java collections) を使用して辞書を実装しようとしています。過去の誰かの例を切り捨てました。

【エントリー.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;
    }
}

LinkedList の Java コレクションから「挿入」および「検索」機能を使用する方法の例を教えてください。別のインデックスが必要ですか? KとVのほかに。

事前にどうもありがとうございました。

4

1 に答える 1

0

マップインターフェイスはあなたが探しているものです。Javadocによると：

Dictionaryクラスは、キーを値にマップするHashtableなどのクラスの抽象親です。すべてのキーとすべての値はオブジェクトです。1つのDictionaryオブジェクトでは、すべてのキーが最大で1つの値に関連付けられます。辞書とキーが与えられると、関連する要素を検索できます。null以外のオブジェクトは、キーおよび値として使用できます。原則として、このクラスの実装では、2つのキーが同じであるかどうかを判断するために、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");
    }
}

この例は、バケット（この場合はLinkedList）を使用して衝突を回避する方法も示しています。このメソッドは呼び出されます。seperate chaining

于 2013-01-22T23:45:08.663 に答える