算法(5)哈希表

830 阅读4分钟

1.0 问题描述

实现数据结构:哈希表。

2.0 问题分析

  1. 哈希表可以看作我们经常使用的字典(swift)或对象(js),可以让一个key&value对一一对应,可以快速根据key找到value。
  2. 哈希表内部使用数组实现,我们需要将不论任何类型的key计算出与之一一对应的数字来,数字的大小介于0到数组尺寸之间,这样,我们可以把value直接存储到数组的对应位置。
  3. 通过key计算出唯一数字的过程,叫做哈希函数。同一个key每次通过hash函数生成的数字都是相同的。
  4. 由于不同的key可能会生成相同的数字,这种情况叫做哈希冲突。由于冲突不可避免,所以我们有多种办法来处理冲突。
  5. 处理冲突的方法有:
  • 开放定址法:如果数字相同,则令数字加1,查看数组中是否有值,直到找到空位
  • 链表法:数组每个位置带一个链表,链表中存储冲突的数值
  • 再次散列:多次调用散列函数,直到不冲突
  • 公共溢出区:将冲突的值放到另外一个数组中,一旦冲突,则去新数组查找。
  1. 使用较多的方法是开放定址法。
  2. 为了提升性能,我们需要选择更好的哈希函数,还需要保持较低的填充因子,填充因子=已存储的数量/当前数组总数,我们需要做2件事情。
  • 让哈希函数的冲突更少
  • 填充因子大于0.75,即将数组扩充至当前尺寸的2倍

3.0 代码实现

3.1使用swift实现



/*
 * 哈希表Key需要遵守的协议
 * 用于生成hash值,即hash函数
 */
public protocol HashedKey {
    var hashValue: UInt32 { get }
}


/*
 * 哈希表内部元素表示
 */
fileprivate struct HashElement<Key, Value>{
    var key: Key;
    var value: Value;
}


/*
 * 哈希表
 */
public class Hash<Key, Value> where Key: HashedKey, Key: Equatable{
    ///内部数组
    private var _storeArr:[HashElement<Key, Value>?];
    ///当前元素数量
    private var _storeCount = 0;
    ///最小元素数量
    private let MINSIZE = 1;
    
    /*
     * 构造方法
     */
    public init() {
        _storeArr = Array<HashElement<Key, Value>?>.init(repeating: nil, count: MINSIZE);
    }
    
    /**
     * 将内部数组的尺寸扩充为2倍大小
     */
    private func _expand(){
        let oldArr = _storeArr;
        _storeArr = Array<HashElement<Key, Value>?>.init(repeating: nil, count: _storeArr.count * 2);
        _storeCount = 0;
        for case let e? in oldArr {
            set(k: e.key, v: e.value);
        }
    }
    
    /**
     * 插入数值
     * @param {Key} - k 插入的key
     * @param {Value} - v 插入的value
     */
    public func set(k: Key, v: Value){
        if let i = self._index(k: k){
            _storeArr[i]?.value = v;
            return;
        }
        let capacity = _storeArr.count;
        let hashValue = k.hashValue;
        var idx = Int(hashValue) % capacity;
        while _storeArr[idx] != nil {
            idx =  (idx + 1) % capacity;
        }
        _storeArr[idx] = HashElement.init(key: k, value: v);
        _storeCount += 1;
        
        if _storeCount >= capacity * 3 / 4 {
            _expand();
        }
    }
    
    /**
     * 查找参数k对应的数组下标值,用于判断元素是否存在
     * @param {Key} - k 传入key值
     * @return {Int?} - 返回数组下标,若key不存在,则返回nil
     */
    private func _index(k: Key) -> Int?{
        let capacity = _storeArr.count;
        var idx = Int(k.hashValue) % capacity;
        var count = 0;
        while _storeArr[idx] != nil && _storeArr[idx]!.key != k && count < capacity {
            idx = (idx + 1) % capacity;
            count += 1;
        }
        if _storeArr[idx] != nil && count < capacity {
            return idx;
        }else{
            return nil;
        }
    }
    
    /**
     * 获取数值
     * @param {Key} - k 想要获取数值的key
     * @return {Value?} - 返回的value
     */
    public func get(k: Key) -> Value?{
        if let i = self._index(k: k){
            return _storeArr[i]?.value;
        }else{
            return nil;
        }
    }
    
    /**
     * 支持如下操作:
     * hash[key] = value
     * let v = hash[key]
     */
    public subscript(k: Key)->Value?{
        set{
            if case let v? = newValue {
                set(k: k, v: v)
            }
        }
        get{
            return get(k: k);
        }
    }
}

3.2使用js实现

function Hash(hashFunction) {
    this._elements = new Array(1);
    this._elementsCount = 0;
    this._hashFunc = hashFunction;
}


Hash.prototype._expand = function(){
    let capacity = this._elements.length;
    let oldElements = this._elements;
    this._elements = new Array(capacity * 2);
    oldElements.forEach(element => {
        this.set(element.key, element.value);
    });
}


Hash.prototype.set = function(k, v){
    let index = this._index(k);
    if(index != undefined && this._elements[index] != v){
        this._elements[index] = v;
        return;
    }
    let capacity = this._elements.length;
    let hashValue = this._hashFunc(k) % capacity;
    while (this._elements[hashValue]) {
        hashValue = (hashValue + 1) % capacity;
    }
    this._elements[hashValue] = {key:k, value:v};
    this._elementsCount++;


    if(this._elementsCount >= capacity * 3 / 4){
        this._expand();
    }
}


Hash.prototype._index = function(k){
    let capacity = this._elements.length;
    let hashValue = this._hashFunc(k) % capacity;
    let count = 0;
    while(this._elements[hashValue] && this._elements[hashValue].key != k && count < capacity){
        hashValue = (hashValue + 1) % capacity;
        count++;
    }
    if(this._elements[hashValue] && count < capacity){
        return hashValue;
    }
}


Hash.prototype.get = function(k){
    let index = this._index(k);
    if(index != undefined) {
        return this._elements[index];
    }
}

4.0 复杂度分析

  1. 插入值
  • 我们通过哈希函数计算一个数组下标,只有这一次计算。
  • 下标可能有冲突,冲突的数量是常数级。这一点我们通过良好的哈希函数,和较低的填充因子来保证。
  • 当填充因子达到上限,需要创建新的数组并copy所有数值到新数组中。这一步操作需要O(n)的时间,但是把这一步均摊到之前每一个set函数中,我们会发现相当于每个set的时间乘以2,也是常数级别。
  • 综上所述,hash表插入的时间复杂度为O(1)。
  1. 获取值
  • 获取值的过程类似于插入,也是计算一次哈希函数。
  • 如果有冲突,则根据规则继续操作,通过上面的分析,我们知道,这一步也是常数级别的时间复杂度。
  • 综上所述,hash表获取值的时间复杂度也是O(1)。