Skip to main content

哈希表 HashTable

哈希表的概念​

哈希表的实现方式​

数组 vs 链表​

数组

  • 寻址容易，插入和删除元素困难

链表

  • 寻址困难，插入和删除元素容易

哈希表: 数组 + 链表​

图左侧竖项为数组，每个数组的值为链表。

插入键值对演示​

X => f(X) = M => M % Array.length => Position

哈希函数 (Hash Function)​

哈希函数能快速将一个数值转换成哈希值(整数)。所以哈希表必须保持哈希值的计算一致，如果两个哈希值是不相同的，那么这两个哈希值的原始输入也是不相同的。

那如果两个不同的输入得到相同的哈希值 = 哈希值冲突

我们输入关键字 x, 使用哈希函数 f(x) 计算出哈希值 y, 然后使用哈希值 y 来找到特定的数组下标，并在对应位置插入新数据。

X => f(X) = Y => Y % Array.length => Array position of X

插入键值对的过程详解​

哈希表支持的操作​

  • add(Key key, Value value): 将一对新的键值对加入哈希表
  • get(Key key): 通过特定的关键字拿到其所对应的数值
  • remove(Key key): 通过关键字，删除哈希表中的数值对
  • getSize(): 当前键值对的数量
  • isEmpty(): 查看哈希表是否为空

代码实现​

import java.util.ArrayList;

public class HashMap {
    static class HashNode<String, Integer> {
        String key;
        Integer value;
        HashNode<String, Integer> next;
        public HashNode(String key, Integer value) {
            this.key  = key;
            this.value = value;
        }
    }

    private ArrayList<HashNode<String, Integer>> bucketArray;
    private int numBuckets;
    private int size;

    public HashMap() {
        bucketArray = newArrayList<>();
        numBuckets = 10;
        size = 0;
        for (int i = 0; i < numBuckets; i++) {
            bucketArray.add(null);
        }
    }

    private int getBucketIndex(String key) {
        int hashCode = key.hashCode();
        int index = hashCode % numBuckets;
        return index;
    }

    public void add(String key, Integer value) {
        int bucketIndex = getBucketIndex(key);
        HashNode<String, Integer> head = bucketArray.get(bucketIndex);
        while(head != null) {
            if(head.key.equals(key)) {
                head.value = value;
                return;
            }
            head = head.next;
        }
        head = bucketArray.get(bucketIndex);
        HashNode<String, Integer> newNode = new HashNode<String, Integer>(key, value);
        newNode.next = head;
        bucketArray.set(bucketIndex, newNode);
        size++;
        // 扩充条件
        if((1.0 * size) / numBuckets >= 0.7) {
            generateBiggerArray();
        }
    }

    private void generateBiggerArray() {
        ArrayList<HashNode<String, Integer>> temp = bucketArray;
        bucketArray = new ArrayList<>();
        numBuckets = 2 * numBuckets;
        for (int i = 0; i < numBuckets; i++) {
            bucketArray.add(null);
        }
        size = 0;
        for (HashNode<String, Integer> headNode : temp) {
            while(headNode != null) {
                add(headNode.key, headNode.value);
                headNode = headNode.next;
            }
        }
    }

    public Integer get(String key) {
        int bucketIndex = getBucketIndex(key);
        HashNode<String, Integer> head = bucketArray.get(bucketIndex);
        wihile(head != null) {
            if(head.key.equals(key)) {
                return head.value;
            }
            head = head.next;
        }
        return null;
    }

    public Integer remove(String key) {
        int bucketIndex = getBucketIndex(key);
        HashNode<String, Integer> head = bucketArray.get(bucketIndex);
        HashNode<Stirng, Integer> prev = null;

        while(head != null) {
            if(head.key.equals(key)) {
                break;
            }
            prev = head;
            head = head.next;
        }

        if(head == null) {
            return null;
        }

        if(prev != null) {
            prev.next = head.next;
        } else { // Corner case: Delte the head node
            bucketArray.set(bucketIndex, head.next);
        }

        size--;

        return head.value;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

来源​