哈希表

简单哈希表

class Pair {
	constructor(key, value) {
		this.key = key
		this.value = value
	}
}

class Hash {
	constructor() {
		this.buckets = new Array(100).fill(null)
	}

	hashFunction(key) {
		return key % 100
	}

	set(key, value) {
		const index = this.hashFunction(key)
		this.buckets[index] = new Pair(key, value)
	}

	delete(key) {
		const index = this.hashFunction(key)
		this.buckets[index] = null
	}

	get(key) {
		const index = this.hashFunction(key)
		const pair = this.buckets[index]
		if (pair === null) return null
		return pair
	}

	keys() {
		const arr = []
		for (let i = 0; i < this.buckets.length; i++) {
			if (this.buckets[i] !== null) arr.push(this.buckets[i].key)
		}
		return arr
	}

	values() {
		const arr = []
		for (let i = 0; i < this.buckets.length; i++) {
			if (this.buckets[i] !== null) arr.push(this.buckets[i].value)
		}
		return arr
	}

	entries() {
		const arr = []
		for (let i = 0; i < this.buckets.length; i++) {
			if (this.buckets[i] !== null) arr.push(this.buckets[i])
		}
		return arr
	}
}

链表法解决哈希冲突

建立桶数组，每个数组元素是一个桶链表，将哈希值相同的数据进行链表管理

class Pair {
	constructor(key, value) {
		this.key = key
		this.value = value
	}
}

class Hash {
	constructor() {
		this.size = 0
		this.capacity = 100
		this.loadThres = 2 / 3
		this.extendRatio = 2
		this.buckets = new Array(this.capacity).fill(null).map(x => [])
	}

	hashFun(key) {
		return key % this.capacity
	}

	loadFactor() {
		return this.size / this.capacity
	}

	extend() {
		const tempBucket = this.buckets
		this.capacity *= this.extendRatio
		this.buckets = new Array(this.capacity).fill(null).map(x=>[])
		this.size = 0
		for(let i = 0 ;i < tempBucket.length; i++) {
			for(let j = 0; j < tempBucket[i]; j++) {
				this.set(tempBucket[i][j].key,tempBucket[i][j].value)
			}
		}
	}

	get(key) {
		const index = this.hashFun(key)
		const bucket = this.buckets[index]
		for (let i = 0; i < bucket.length; i++) {
			if (bucket[i].key === key) return bucket[i].value
		}
		return null
	}

	set(key, value) {
		if(this.loadFactor > this.loadThres) {
			this.extend()
		}
		const index = this.hashFun(key)
		const bucket = this.buckets[index]
		for (let i = 0; i < bucket.length; i++) {
			if (bucket[i].key === key) {
				bucket[i].value = value
				return
			}
		}
		const pair = new Pair(key, value)
		bucket.push(pair)
		this.size++
	}

	delete(key) {
		const index = this.hashFun(key)
		const bucket = this.buckets[index]
		for(let i = 0; i < bucket.length; i++) {
			if(bucket[i].key === key) {
				bucket.splice(i,1)
				this.size--
				return
			}
		}
	}
	
}

线性探测法解决哈希冲突

当哈希值相同时，往后寻找最近的空桶并填入

删除元素利用了懒惰删除，解决了指针查找到为null而跳出的情况

class Pair {
	constructor(key, value) {
		this.key = key
		this.value = value
	}
}

class Hash {
	constructor() {
		this.size = 0
		this.capacity = 100
		this.loadThres = 2 / 3
		this.extendRatio = 2
		this.buckets = new Array(this.capacity).fill(null)
		this.deleteFlag = new Pair(-1, '-1')
	}

	hashFun(key) {
		return key % this.capacity
	}

	loadFactor() {
		return this.size / this.capacity
	}

	findBucket(key) {
		const index = this.hashFun(key)
		while (this.buckets[index] !== null) {
			if (this.buckets[index].key === key) {
				return index
			}
			index = index + 1
		}
		return index
	}

	extend() {
		const tempBucket = this.buckets
		this.capacity *= this.extendRatio
		this.buckets = new Array(this.capacity).fill(null)
		this.size = 0
		for (let i = 0; i < tempBucket; i++) {
			if (tempBucket[i] !== null && tempBucket[i] !== this.deleteFlag) {
				this.set(tempBucket[i].key, tempBucket[i].value)
			}
		}
	}

	get(key) {
		const index = this.findBucket(key)
		if (
			this.buckets[index] !== null &&
			this.buckets[index] !== this.deleteFlag
		)
			return this.buckets[index].value
		return null
	}

	set(key, value) {
		if (this.loadFactor() > this.loadThres) {
			this.extend()
		}
		const index = this.findBucket(key)
		if (
			this.buckets[index] !== null &&
			this.buckets[index] !== this.deleteFlag
		) {
			this.buckets[index].value = value
			return
		}
		this.buckets[index] = new Pair(key, value)
		this.size++
	}

	delete(key) {
		const index = this.findBucket(key)
		if (
			this.buckets[index] === null ||
			this.buckets[index] === this.deleteFlag
		)
			return
		this.buckets[index] = this.deleteFlag
		this.size--
	}
}