数据结构与算法(七) - 哈希表

第八章 哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

代码实现

根据以前的单向链表编写一个哈希链表

public class HashTableList<K, V> {
          
   
    Node<K, V> head;

    public void put(K key, V value) {
          
   
        if (value == null) {
          
   
            throw new NullPointerException();
        }
        Node<K, V> node = new Node<>(key, value);
        if (head == null) {
          
   
            head = node;
            return;
        }
        Node<K, V> temp = head;
        while (temp.next != null) {
          
   
            temp = temp.next;
        }
        temp.next = node;
    }

    public V get(K key) {
          
   
        if (head == null) {
          
   
            return null;
        }
        Node<K, V> temp = head;
        while (true) {
          
   
            if (temp.key == key) {
          
   
                return temp.value;
            }
            if (temp.next == null) {
          
   
                break;
            }
            temp = temp.next;
        }
        return null;
    }

    @Override
    public String toString() {
          
   
        StringJoiner sj = new StringJoiner(",", "[", "]");
        Node<K, V> temp = head;
        while (temp != null) {
          
   
            sj.add(temp.toString());
            temp = temp.next;
        }
        return sj.toString();
    }


    private static class Node<K, V> {
          
   
        K key;
        V value;
        Node<K, V> next;

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

        @Override
        public String toString() {
          
   
            return key + "=" + value;
        }
    }
}

哈希表

public class MyHashTable<K, V> {
          
   
    private final HashTableList<K, V>[] table;
    private final int size;

    public MyHashTable(int size) {
          
   
        this.size = size;
        this.table = new HashTableList[size];
        for (int i = 0; i < size; i++) {
          
   
            table[i] = new HashTableList<>();
        }
    }

    public void put(K key, V value) {
          
   
        int hash = key.hashCode();
        int index = hashFun(hash);
        table[index].put(key, value);
    }

    public void list() {
          
   
        for (int i = 0; i < size; i++) {
          
   
            String str = table[i].toString();
            System.out.printf("hash[%d]:%s
", i, str);
        }
    }

    public V get(K key) {
          
   
        int hashCode = key.hashCode();
        int index = hashFun(hashCode);
        return table[index].get(key);
    }

    // 编写散列函数, 使用一个简单取模法
    public int hashFun(int id) {
          
   
        return Math.abs(id) % size;
    }

}

演示

public class HashTableDemo {
          
   
    public static void main(String[] args) {
          
   
        Student s1 = new Student(1L, "肖战", 15, true);
        Student s2 = new Student(2L, "王一博", 15, true);
        Student s3 = new Student(3L, "杨紫", 17, false);
        Student s4 = new Student(4L, "李现", 18, true);

        MyHashTable<String, Student> hashtable = new MyHashTable<>(8);
        hashtable.put("a", s1);
        hashtable.put("b", s2);
        hashtable.put("i", s3);
        hashtable.put("d", s4);
        hashtable.list();
        System.out.println(hashtable.get("a"));

    }
}

运行结果如下

hash[0]:[]
hash[1]:[a=Student(id=1, name=肖战, age=15, isMale=true),i=Student(id=3, name=杨紫, age=17, isMale=false)]
hash[2]:[b=Student(id=2, name=王一博, age=15, isMale=true)]
hash[3]:[]
hash[4]:[d=Student(id=4, name=李现, age=18, isMale=true)]
hash[5]:[]
hash[6]:[]
hash[7]:[]
Student(id=1, name=肖战, age=15, isMale=true)