1.0 问题描述
实现数据结构：哈希表。
2.0 问题分析
- 哈希表可以看作我们经常使用的字典（swift）或对象（js），可以让一个key&value对一一对应，可以快速根据key找到value。
- 哈希表内部使用数组实现，我们需要将不论任何类型的key计算出与之一一对应的数字来，数字的大小介于0到数组尺寸之间，这样，我们可以把value直接存储到数组的对应位置。
- 通过key计算出唯一数字的过程，叫做哈希函数。同一个key每次通过hash函数生成的数字都是相同的。
- 由于不同的key可能会生成相同的数字，这种情况叫做哈希冲突。由于冲突不可避免，所以我们有多种办法来处理冲突。
- 处理冲突的方法有：
- 开放定址法：如果数字相同，则令数字加1，查看数组中是否有值，直到找到空位
- 链表法：数组每个位置带一个链表，链表中存储冲突的数值
- 再次散列：多次调用散列函数，直到不冲突
- 公共溢出区：将冲突的值放到另外一个数组中，一旦冲突，则去新数组查找。
- 使用较多的方法是开放定址法。
- 为了提升性能，我们需要选择更好的哈希函数，还需要保持较低的填充因子，填充因子=已存储的数量/当前数组总数，我们需要做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 复杂度分析
- 插入值
- 我们通过哈希函数计算一个数组下标，只有这一次计算。
- 下标可能有冲突，冲突的数量是常数级。这一点我们通过良好的哈希函数，和较低的填充因子来保证。
- 当填充因子达到上限，需要创建新的数组并copy所有数值到新数组中。这一步操作需要O(n)的时间，但是把这一步均摊到之前每一个set函数中，我们会发现相当于每个set的时间乘以2，也是常数级别。
- 综上所述，hash表插入的时间复杂度为O(1)。
- 获取值
- 获取值的过程类似于插入，也是计算一次哈希函数。
- 如果有冲突，则根据规则继续操作，通过上面的分析，我们知道，这一步也是常数级别的时间复杂度。
- 综上所述，hash表获取值的时间复杂度也是O(1)。
