哈希表 - HashTable

基本概念

哈希表是一种特殊的数据结构，通过索引，能快速的查找到某个元素。

	put	get
List	O(n)	O(n)
Balanced BST	O(logn)	O(logn)
Hash Table	O(1)	O(1)

设计原理

通过哈希函数，将key映射到value上。

• Java 中哈希的实现

Balanced BST	HashTable
TreeSet	HashSet
TreeMap	HashMap

哈希函数 (hash function)

确定性，不可逆性。
输入任何二进制数据，输出整数。
在密码学也有广泛应用。
一个好的哈希函数，要在给定的输入范围内，尽可能少的发生碰撞；而且计算复杂度不能太高。

• 除余法(modulo division)

// Java String hashcode
for (char c : str) {
    hashCode = 31 * hashCode + c;
}

• 平方取中法(mid-square)
• 基数转换法(radix transformation)

冲突解决(collision)

• 开散列(open hashing)
  开辟一个数组
  数组的每一个元素是一个链表的头结点的引用
  通过Hash函数，计算key对应的index，将index相同的key-value插入到同 一个链表中
• 闭散列(closed hashing)
  open addressing
  开辟一个数组，一个位置只放一个key-value
  通过Hash函数，计算key对应的index，将key-value放在相应的位置
  如果这个位置已经有了元素，则查找其他合适的空位置放入
  线性探查 (linear probing)
  二次探查 (quadratic probing)
  随机探查 (random probing)
  双散列探查 (double hashing)

重哈希(rehashing)

当哈希表中的元素越来越多的时候，冲突的几率也就越来越高。为了提高查询的效率，就要对哈希表进行扩容。
负载因子(load factor) : 哈希表中的元素个数除以哈希表的容量。
哈希表检索的时间与负载因子有关, 当负载因子小于0.5时，大部分检索长度小于2; 当负载因子大于0.5时，性能急剧下降。这是一种空间换时间的方法。
重哈希就是调整哈希表的大小，并将元素重新摆放。
当哈希表过于稀疏，可以节省空间。
当哈希表过于稠密，可以加速查找。

实现

• 基本操作
  查找
  添加
  删除
  平均来说各操作的时间复杂度为O(1)，但最坏情况会到O(n)。因为在添加的过程中会出现碰撞和重哈希的过程。
• 定义HashMap接口

public interface Map {
    void put(String key, String val);
    String get(String key);
}

• 定义键值对

public class Pair {
    String key;
    String val;
    Pair(String key, String val) {
        this.key = key;
        this.val = val;
    }
}

• 使用open hashing解决collision
  separate chaining方法

class ListNode {
    Pair pair;
    ListNode next;
    ListNode(Pair pair) {
        this.pair = pair;
        next = null;
    }
}

public class openHashingMap implements Map {
    private ListNode[] data;
    private int capacity;
    private int size;
    private static final float LOAD_FACTOR = 0.75f; // 设置loadFactor为0.75
    public openHashingMap() {
        capacity = 16;
        size = 0;
        data = new ListNode[capacity];
    }
    public openHashingMap(int capacity) {
        this.capacity = capacity;
        size = 0;
        data = new ListNode[capacity];
    }
    @Override 
    public void put(String key, String val) {
        if (key == null) return;
        if (size >= capacity * LOAD_FACTOR) {
            rehashing();
        }
        int index = key.hashCode() % capacity; // 使用Java自带的String.hashCode()当做hash function
        ListNode cur = data[index];
        while (cur != null) {
            if (cur.pair.key.equals(key)) {
                // map中已经有这个key了，更新value
                cur.pair.val = val;
                return;
            }
            cur = cur.next;
        }
        // map中没有这个key，在这个index添加新节点
        ListNode newNode = new ListNode(new Pair(key, val));
        newNode.next = data[index];
        data[index] = newNode;
        size++;
    }
    @Override
    public String get(String key) {
        if (key == null) {
            return null;
        }
        int index = key.hashCode() % capacity;
        ListNode cur = data[index];
        while (cur != null) {
            if (cur.pair.key.equals(key)) {
                return cur.pair.val;
            }
            cur = cur.next;
        }
        return null;
    }
    // 重哈希扩大为原容量的2倍
    private void rehashing() {
        int newCapacity = capacity * 2;
        ListNode[] newData = new ListNode[newCapacity];
        for (int i = 0; i < capacity; ++i) {
            ListNode cur = data[i];
            while (cur != null) {
                ListNode tmp = cur;
                cur = cur.next;
                int newIndex = tmp.pair.key.hashCode() % newCapacity;
                tmp.next = newData[newIndex];
                newData[newIndex] = tmp;
            }
        }
        capacity = newCapacity;
        data = newData;
    }
}

• 使用closed hashing解决collision
  linear probing 方法

public class LPHashing implements Map{
    private Pair[] data = null;
    private int capacity = 0;
    public LPHashing() {
        capacity = 16;
        data = new Pair[capacity];
    }
    public LPHashing(int capacity) {
        this.capacity = capacity;
        data = new Pair[capacity];
    }
    @Override
    public void put(String key, String val) {
        if (key == null) return;
        int index = key.hashCode() % capacity;
        for (int i = 0; i < capacity; ++i) {
            int cur = (index + i) % capacity;
            if (data[cur] == null) {
                data[cur] = new Pair(key, val);
                return;
            } else if (data[cur].key.equals(key)) {
                data[cur].val = val;
                return;
            }
        }
        throw new IllegalStateException("HashMap is already full");
    }
    @Override
    public String get(String key) {
        if (key == null) {
            return null;
        }
        int index = key.hashCode() % capacity;
        for (int i = 0; i < capacity; ++i) {
            int cur = (index + i) % capacity;
            if (data[cur] == null) {
                return null;
            } else if (data[cur].key.equals(key)) {
                return data[cur].val;
            }
        }
        return null;
    }
}

Lintcode 相关练习

Count Characters
Strobogrammatic Number
two sum
Anagrams
Copy List with Random Pointer