Melaksanakan Peta Menggunakan Hashing

Peta boleh dilaksanakan menggunakan pencincangan. Kini anda memahami konsep pencincangan. Anda tahu cara mereka bentuk fungsi cincang yang baik untuk memetakan kunci kepada indeks dalam jadual cincang, cara mengukur prestasi menggunakan faktor beban dan cara meningkatkan saiz jadual dan cincang untuk mengekalkan prestasi. Bahagian ini menunjukkan cara melaksanakan peta menggunakan rantaian berasingan.

Kami mereka bentuk antara muka Peta tersuai kami untuk mencerminkan java.util.Map dan menamakan antara muka MyMap dan kelas konkrit MyHashMap , seperti yang ditunjukkan dalam Rajah di bawah.

Bagaimana anda melaksanakan MyHashMap? Jika anda menggunakan ArrayList dan menyimpan entri baharu pada penghujung senarai, masa carian ialah O(n). Jika anda melaksanakan MyHashMap menggunakan pokok binari, masa carian akan menjadi O(log n) jika pokok itu seimbang. Namun begitu, anda boleh melaksanakan MyHashMap menggunakan pencincangan untuk mendapatkan algoritma carian masa O(1). Kod di bawah menunjukkan antara muka MyMap.

package demo;

public interface MyMap<K, V> {
    /** Remove all of the entries from this map */
    public void clear();

    /** Return true if the specified key is in the map */
    public boolean containsKey(K key);

    /** Return true if this map contains the specified value */
    public boolean containsValue(V value);

    /** Return a set of entries in the map */
    public java.util.Set<Entry<K, V>> entrySet();

    /** Return the value that matches the specified key */
    public V get(K key);

    /** Return true if this map doesn't contain any entries */
    public boolean isEmpty();

    /** Return a set consisting of the keys in this map */
    public java.util.Set<K> keySet();

    /** Add an entry (key, value) into the map */
    public V put(K key, V value);

    /** Remove an entry for the specified key */
    public void remove(K key);

    /** Return the number of mappings in this map */
    public int size();

    /** Return a set consisting of the values in this map */
    public java.util.Set<V> values();

    /** Define an inner class for Entry */
    public static class Entry<K, V> {
        K key;
        V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        @Override
        public String toString() {
            return "[" + key + ", " + value + "]";
        }
    }
}

Kod di bawah melaksanakan MyHashMap menggunakan rantaian berasingan.

package demo;
import java.util.LinkedList;

public class MyHashMap<K, V> implements MyMap<K, V> {
    // Define the default hash-table size. Must be a power of 2
    private static int DEFAULT_INITIAL_CAPACITY = 4;

    // Define the maximum hash-table size. 1 << 30 is same as 2^30
    private static int MAXIMUM_CAPACITY = 1 << 30;

    // Current hash-table capacity. Capacity is a power of 2
    private int capacity;

    // Define default load factor
    private static float DEFAULT_MAX_LOAD_FACTOR = 0.75f;

    // Specify a load factor used in the hash table
    private float loadFactorThreshold;

    // The number of entries in the map
    private int size = 0;

    // Hash table is an array with each cell being a linked list
    LinkedList<MyMap.Entry<K, V>>[] table;

    /** Construct a map with the default capacity and load factor */
    public MyHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);
    }

    /** Construct a map with the specified initial capacity and
     * default load factor */
    public MyHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);
    }

    /** Construct a map with the specified initial capacity
     * and load factor */
    public MyHashMap(int initialCapacity, float loadFactorThreshold) {
        if(initialCapacity > MAXIMUM_CAPACITY)
            this.capacity = MAXIMUM_CAPACITY;
        else
            this.capacity = trimToPowerOf2(initialCapacity);

        this.loadFactorThreshold = loadFactorThreshold;
        table = new LinkedList[capacity];
    }

    @Override /** Remove all of the entries from this map */
    public void clear() {
        size = 0;
        removeEntries();
    }

    @Override /** Return true if the specified key is in the map */
    public boolean containsKey(K key) {
        if(get(key) != null)
            return true;
        else
            return false;
    }

    @Override /** Return true if this map contains the value */
    public boolean containsValue(V value) {
        for(int i = 0; i < capacity; i++) {
            if(table[i] != null) {
                LinkedList<Entry<K ,V>> bucket = table[i];
                for(Entry<K, V> entry: bucket)
                    if(entry.getValue().equals(value))
                        return true;
            }
        }

        return false;
    }

    @Override /** Return a set of entries in the map */
    public java.util.Set<MyMap.Entry<K, V>> entrySet() {
        java.util.Set<MyMap.Entry<K, V>> set = new java.util.HashSet<>();

        for(int i = 0; i < capacity; i++) {
            if(table[i] != null) {
                LinkedList<Entry<K, V>> bucket = table[i];
                for(Entry<K, V> entry: bucket)
                    set.add(entry);
            }
        }

        return set;
    }

    @Override /** Return the value that matches the specified key */
    public V get(K key) {
        int bucketIndex = hash(key.hashCode());
        if(table[bucketIndex] != null) {
            LinkedList<Entry<K, V>> bucket = table[bucketIndex];
            for(Entry<K, V> entry: bucket)
                if(entry.getKey().equals(key))
                    return entry.getValue();
        }

        return null;
    }

    @Override /** Return true if this map contains no entries */
    public boolean isEmpty() {
        return size == 0;
    }

    @Override /** Return a set consisting of the keys in this map */
    public java.util.Set<K> keySet() {
        java.util.Set<K> set = new java.util.HashSet<K>();

        for(int i = 0; i < capacity; i++) {
            if(table[i] != null) {
                LinkedList<Entry<K, V>> bucket = table[i];
                for(Entry<K, V> entry: bucket)
                    set.add(entry.getKey());
            }
        }

        return set;
    }

    @Override /** Add an entry (key, value) into the map */
    public V put(K key, V value) {
        if(get(key) != null) { // The key is already in the map
            int bucketIndex = hash(key.hashCode());
            LinkedList<Entry<K, V>> bucket = table[bucketIndex];
            for(Entry<K, V> entry: bucket)
                if(entry.getKey().equals(key)) {
                    V oldValue = entry.getValue();
                    // Replace old value with new value
                    entry.value = value;
                    // Return the old value for the key
                    return oldValue;
                }
        }

        // Check load factor
        if(size >= capacity * loadFactorThreshold) {
            if(capacity == MAXIMUM_CAPACITY)
                throw new RuntimeException("Exceeding maximum capacity");

            rehash();
        }

        int bucketIndex = hash(key.hashCode());

        // Create a linked list for the bucket if not already created
        if(table[bucketIndex] == null) {
            table[bucketIndex] = new LinkedList<Entry<K, V>>();
        }

        // Add a new entry (key, value) to hashTable[index]
        table[bucketIndex].add(new MyMap.Entry<K, V>(key, value));

        size++; // Increase size

        return value;
    }

    @Override /** Remove the entries for the specified key */
    public void remove(K key) {
        int bucketIndex = hash(key.hashCode());

        // Remove the first entry that matches the key from a bucket
        if(table[bucketIndex] != null) {
            LinkedList<Entry<K, V>> bucket = table[bucketIndex];
            for(Entry<K, V> entry: bucket)
                if(entry.getKey().equals(key)) {
                    bucket.remove(entry);
                    size--; // Decrease size
                    break; // Remove just one entry that matches the key
                }
        }
    }

    @Override /** Return the number of entries in this map */
    public int size() {
        return size;
    }

    @Override /** Return a set consisting of the values in this map */
    public java.util.Set<V> values() {
        java.util.Set<V> set = new java.util.HashSet<>();

        for(int i = 0; i < capacity; i++) {
            if(table[i] != null) {
                LinkedList<Entry<K, V>> bucket = table[i];
                for(Entry<K, V> entry: bucket)
                    set.add(entry.getValue());
            }
        }

        return set;
    }

    /** Hash function */
    private int hash(int hashCode) {
        return supplementalHash(hashCode) & (capacity - 1);
    }

    /** Ensure the hashing is evenly distributed */
    private static int supplementalHash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    /** Return a power of 2 for initialCapacity */
    private int trimToPowerOf2(int initialCapacity) {
        int capacity = 1;
        while(capacity < initialCapacity) {
            capacity <<= 1; // Same as capacity *= 2. <= is more efficient
        }

        return capacity;
    }

    /** Remove all entries from each bucket */
    private void removeEntries() {
        for(int i = 0; i < capacity; i++) {
            if(table[i] != null) {
                table[i].clear();
            }
        }
    }

    /** Rehash the map */
    private void rehash() {
        java.util.Set<Entry<K, V>> set = entrySet(); // Get entries
        capacity <<= 1; // Same as capacity *= 2. <= is more efficient
        table = new LinkedList[capacity]; // Create a new hash table
        size = 0; // Reset size to 0

        for(Entry<K, V> entry: set) {
            put(entry.getKey(), entry.getValue()); // Store to new table
        }
    }

    @Override /** Return a string representation for this map */
    public String toString() {
        StringBuilder builder = new StringBuilder("[");

        for(int i = 0; i < capacity; i++) {
            if(table[i] != null && table[i].size() > 0)
                for(Entry<K, V> entry: table[i])
                    builder.append(entry);
        }

        builder.append("]");
        return builder.toString();
    }
}

Kelas MyHashMap melaksanakan antara muka MyMap menggunakan rantaian berasingan. Parameter yang menentukan saiz jadual cincang dan faktor beban ditakrifkan dalam kelas. Kapasiti awal lalai ialah 4 (baris 5) dan kapasiti maksimum ialah 2^30 (baris 8). Jadual cincang semasa
kapasiti direka bentuk sebagai nilai kuasa 2 (baris 11). Ambang faktor beban lalai ialah 0.75f (baris 14). Anda boleh menentukan ambang faktor beban tersuai semasa membina peta. Ambang faktor beban tersuai disimpan dalam loadFactorThreshold (baris 17). Medan data saiz menandakan bilangan entri dalam peta (baris 20). Jadual cincang ialah tatasusunan. Setiap sel dalam tatasusunan ialah senarai terpaut (baris 23).

Tiga pembina disediakan untuk membina peta. Anda boleh membina peta lalai dengan kapasiti lalai dan ambang faktor beban menggunakan pembina no-arg (baris 26–28), peta dengan kapasiti yang ditentukan dan ambang faktor beban lalai (baris 32–34), dan peta dengan kapasiti dan ambang faktor beban yang ditentukan (garisan 38–46).

Kaedah jelas mengalih keluar semua entri daripada peta (baris 49–52). Ia memanggil removeEntries(), yang memadamkan semua entri dalam baldi (baris 221–227). Kaedah removeEntries() mengambil masa O(capacity) untuk mengosongkan semua entri dalam jadual.

Kaedah containsKey(key) menyemak sama ada kunci yang ditentukan berada dalam peta dengan menggunakan kaedah get (baris 55–60). Memandangkan kaedah get mengambil masa O(1), kaedah containsKey(key) mengambil masa O(1).

Kaedah containsValue(value) menyemak sama ada nilai itu berada dalam peta (baris 63–74). Kaedah ini mengambil masa O(kapasiti + saiz). Ia sebenarnya O(kapasiti), kerana saiz kapasiti 7.

Kaedah entrySet() mengembalikan set yang mengandungi semua entri dalam peta (baris 77–90). Kaedah ini mengambil masa O(kapasiti).

Kaedah get(key) mengembalikan nilai entri pertama dengan kunci yang ditentukan (baris 93–103). Kaedah ini mengambil masa O(1).

Kaedah isEmpty() hanya mengembalikan benar jika peta kosong (baris 106–108). Kaedah ini mengambil masa O(1).

Kaedah keySet() mengembalikan semua kunci dalam peta sebagai set. Kaedah ini mencari kunci daripada setiap baldi dan menambahkannya pada set (baris 111–123). Kaedah ini mengambil masa O(kapasiti).

Kaedah put(kunci, nilai) menambah kemasukan baharu ke dalam peta. Kaedah pertama menguji jika kunci sudah ada dalam peta (baris 127), jika ya, ia mencari entri dan menggantikan nilai lama dengan nilai baru dalam entri untuk kunci (baris 134) dan nilai lama dikembalikan ( baris 136). Jika kunci baharu dalam peta, entri baharu dibuat dalam peta (baris 156). Sebelum memasukkan entri baharu, kaedah menyemak sama ada saiz melebihi ambang faktor beban (baris 141). Jika ya, program memanggil rehash() (baris 145) untuk meningkatkan kapasiti dan menyimpan entri ke dalam jadual cincang yang lebih besar yang baharu.

Kaedah rehash() mula-mula menyalin semua entri dalam set (baris 231), menggandakan kapasiti (baris 232), mencipta jadual cincang baharu (baris 233) dan menetapkan semula saiz kepada 0 (baris 234). Kaedah kemudian menyalin masukan ke dalam jadual cincang baharu (baris 236–238). Kaedah rehash mengambil masa O(kapasiti). Jika tiada ulangan dilakukan, kaedah put mengambil masa O(1) untuk menambah entri baharu.

Kaedah buang(kunci) mengalih keluar masukan dengan kunci yang ditentukan dalam peta (baris 164–177). Kaedah ini mengambil masa O(1).

Kaedah size() hanya mengembalikan saiz peta (baris 180–182). Kaedah ini mengambil masa O(1).

Kaedah values() mengembalikan semua nilai dalam peta. Kaedah ini meneliti setiap entri daripada semua baldi dan menambahkannya pada satu set (baris 185–197). Kaedah ini mengambil masa O(kapasiti).

Kaedah cincang() menggunakan Hash tambahan untuk memastikan pencincangan diagihkan sama rata untuk menghasilkan indeks bagi jadual cincang (baris 200–208). Kaedah ini mengambil masa O(1).

Jadual di bawah meringkaskan kerumitan masa kaedah dalam MyHashMap.

Memandangkan pencincangan semula tidak begitu kerap berlaku, kerumitan masa untuk kaedah put ialah O(1). Ambil perhatian bahawa kerumitan kaedah clear, entrySet, keySet, nilai dan rehash bergantung pada kapasiti, jadi untuk mengelakkan prestasi buruk bagi kaedah ini, anda harus memilih kapasiti awal dengan berhati-hati.

Kod di bawah memberikan program ujian yang menggunakan MyHashMap.

Atur cara mencipta peta menggunakan MyHashMap (baris 7) dan menambah lima entri ke dalam peta (baris 8–12). Baris 5 menambah kunci Smith dengan nilai 30 dan baris 9 menambah Smith dengan nilai 65. Nilai terakhir menggantikan nilai sebelumnya. Peta itu sebenarnya hanya mempunyai empat entri. Program ini memaparkan entri dalam peta (baris 14), mendapat nilai untuk kunci (baris 16), menyemak sama ada peta mengandungi kunci (baris 18) dan nilai (baris 19), mengalih keluar masukan dengan kunci Smith (baris 21), dan memaparkan semula entri dalam peta (baris 22). Akhirnya, program mengosongkan peta (baris 24) dan memaparkan peta kosong (baris 25).

Atas ialah kandungan terperinci Melaksanakan Peta Menggunakan Hashing. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!