Data Structure-7 HashTable 哈希表

1. 哈希表

部分理论内容参考自这里。

Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data.

Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the size of the data. Hash Table uses an array as a storage medium and uses hash technique to generate an index where an element is to be inserted or is to be located from.

哈希表：是一种数组形式存储数据索引，联合的数据结构。每个键-值对将会映射到一个唯一的索引，如果我们得到数据的索引，那么我们就可以快速实现对于数据的访问（包括插入和查找）。

2. HashTable 和 HashMap关系

该问题的讨论和答案在此处有详细介绍。

There are several differences between HashMap and Hashtable in Java:

1. Hashtable is synchronized, whereas HashMap is not. This makes HashMap better for non-threaded applications, as unsynchronized Objects typically perform better than synchronized ones.
2. Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.
3. One of HashMap’s subclasses is LinkedHashMap, so in the event that you’d want predictable iteration order (which is insertion order by default), you could easily swap out the HashMap for a LinkedHashMap. This wouldn’t be as easy if you were using Hashtable.

Since synchronization is not an issue for you, I’d recommend HashMap. If synchronization becomes an issue, you may also look at ConcurrentHashMap.

HashMap 和HashTable:除了HashMap是非synchronized而且其可以容纳空值之外，两者几乎是等同的。

1. HashTable 是synchronized的，而HashMap并不是。

2. HashTable不允许空的key-value， 而HashMap允许一个null ke y 和多个null value.

3. HashMap不能保证存入其中的数据顺序保持不变，可以用其子类LinkedHashMap实现。

灰色表明：在JCF(Java Collection Framework)之前，灰色的部分是可用的，包括Vector, HashTable, Stack.

3. HashTable java implementation

该部分代码参考自此处，并对其中的部分内容作过修改。

package com.fqyuan.hashtable;

public class HashTable {
    class LinkedHashEntry {
        private String key;
        private int value;
        private LinkedHashEntry next;

        public LinkedHashEntry(String key, int value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }

    private LinkedHashEntry[] table;
    private int TABLE_SIZE;
    private int size;

    // Constructor:
    public HashTable(int capacity) {
        TABLE_SIZE = capacity;
        table = new LinkedHashEntry[capacity];
        size = ;
    }

    // Function to get number of key-value pair.
    public int getSize() {
        return size;
    }

    // Function to clear hashtable.
    public void makeEmpty() {
        // Do not use size to iterate here, or you'll get error output.
        for (int i = ; i < TABLE_SIZE; i++)
            table[i] = null;
        size = ;
    }

    // Function to get value of a key.
    public int get(String key) {
        int hash = myHash(key) % TABLE_SIZE;
        if (table[hash] == null)
            return -;
        else {
            LinkedHashEntry entry = table[hash];
            while (entry != null && !entry.key.equals(key))
                entry = entry.next;
            if (entry != null)
                return entry.value;
            else
                return -;
        }

    }

    // Function to insert a key-value pair.
    public void insert(String key, int value) {
        int hash = myHash(key) % TABLE_SIZE;
        if (table[hash] == null) {
            table[hash] = new LinkedHashEntry(key, value);
            size++;
        } else {
            LinkedHashEntry entry = table[hash];
            LinkedHashEntry prev = null;
            while (entry != null && !entry.key.equals(key)) {
                prev = entry;
                entry = entry.next;
            }
            if (entry == null) {
                prev.next = new LinkedHashEntry(key, value);
                size++;
            } else {
                // If insert a same key, it will update the key-value pair.
                entry.value = value;
            }
        }
        // size++; //not good here, because insert a duplicate value do not
        // affect the actual size.
    }

    // Function to remove a key-value pair.
    public void remove(String key) {
        int hash = myHash(key) % TABLE_SIZE;
        if (table[hash] == null)
            return;
        else {
            LinkedHashEntry entry = table[hash];
            LinkedHashEntry prev = null;
            while (entry != null && !entry.key.equals(key)) {
                prev = entry;
                entry = entry.next;
            }
            if (entry == null)
                return;
            else {
                if (prev == null)
                    table[hash] = entry.next;
                else
                    prev.next = entry.next;
                size--;
            }
        }
    }

    // Function myHash() which gives a hash value for a given string.
    private int myHash(String key) {
        int hashValue = key.hashCode();
        hashValue %= TABLE_SIZE;
        if (hashValue < )
            hashValue += TABLE_SIZE;
        return hashValue;
    }

    // Function to traverse the hashtable.
    public void traverse() {
        for (int i = ; i < TABLE_SIZE; i++) {
            System.out.print("\nSlot " + (i + ) + ": ");
            LinkedHashEntry entry = table[i];
            while (entry != null) {
                System.out.print(entry.value + " ");
                entry = entry.next;
            }
        }
    }

    public static void main(String[] args) {
        HashTable hashTable = new HashTable();

        hashTable.insert("Ada", );
        hashTable.insert("Basic", );
        hashTable.insert("C", );
        hashTable.insert("C++", );
        hashTable.insert("C#", );
        hashTable.insert("Dog", );
        hashTable.insert("Dog1", );
        hashTable.insert("Dog2", );
        hashTable.insert("Dog3", );
        hashTable.insert("Pascal", );
        hashTable.insert("Fortan", );
        hashTable.insert("Go", );
        hashTable.insert("Java", );
        hashTable.insert("Pascal", );
        hashTable.insert("Pascal0", );
        hashTable.insert("Python", );

        System.out.println(hashTable.getSize());
        hashTable.traverse();

        hashTable.remove("Pascal");
        System.out.print("\n" + hashTable.getSize());
        hashTable.traverse();

        hashTable.makeEmpty();
        System.out.println("\n" + hashTable.getSize());
        hashTable.traverse();
    }
}
           

//Running result:


Slot :  
Slot :    
Slot :         
Slot :    
Slot : 

Slot : 
Slot :    
Slot :         
Slot :    
Slot : 


Slot : 
Slot : 
Slot : 
Slot : 
Slot :