728x90

077. Hash Tables Introduction

What is Hash Tables?

Arrays have indexes and values.

Hash tables have keys and values. You can use keys as an index. It works with hash function.

Hash table’s function is to optimize the nested loop which is O(n^2)

Pros and Conds?

Pros

Fast lookups
Fast inserts
Flexible Keys

(but Good collision resolution required)

Cons

Unordered
Slow key iteration. If you want to grabs all the keys, you need to loop.

In interview, ‘how you will optimize with hash table’ is frequent question.

078. Hash Function

Hash Function?

Simply function that generate values of fixed-sized value.

https://www.md5hashgenerator.com/

Features

멱등성(idempotent)

one way : hard to understand original value with only hash value. ex) 5d41…592?

same input same output.
동일한 요청을 여러번 보내는 것과 한번 보내는 것 간 차이가 없고, 서버 상태도 동일하게 남을 때 HTTP메서드가 멱등성을 가졌다고 함. (MDN)

Performance

Hash function’s performances are different depending on type of hash functions. But we use normally fast one.

079. Hash Collisions

BigO

insert: O(1)
lookup: O(1)
delete: O(1)
search: O(1)

let user = {
  level: 99,
  name: 'John',
  magic: true,
  scream: function() {
    console.log('hello')
  }
}
// This object is stored somewhere in memory.

// But you can access very quickly.
console.log(user.level) //O(1)
user.spell = 'gogogo'; //O(1)
user.scream(); //O(1)

Hash table을 만들면 메모리를 얼마나 할당할지 컴퓨터가 계산한다.

lecture about Hash Tables

https://www.youtube.com/watch?v=KyUTuwz_b7Q&ab_channel=ComputerScience

Open Hasing Algorithm visualization

https://www.cs.usfca.edu/~galles/visualization/OpenHash.html

hash 값은 순차적으로 메모리에 저장되지 않는다.

What is Hash Collision?

‘Hash collision or clash is when two pieces of data in a hash table share the same hash value. The hash value in this case is derived from a hash function which takes a data input and returns a fixed length of bits’, wiki.

Hash collision은 두개의 데이터(2, 15)가 같은 hash value(2)를 공유한다

도표 해체

John Smith의 데이터가 152 bucket에 저장된다
Sandra Dee의 데이터도 152 bucket에 저장된다(Collision)
link list 데이터 구조를 추가로 생성해서 Sandra Dee를 저장한다

link가 길어지면 hash table을 읽고 쓰는 퍼포먼스가 느려진다 -> O(n/k) -> O(n)

resolution for Hash Collision?

separate chaining(including link list)
open addressing

080. Hash Tables In Different Languages

Hash tables are different depending on languages.

ES6 JS에서 객체에서는 Map, Sets 등이 있는데, 객체와 다른 점이 이라면 객체는 string을 키로 하는 반면, map은 함수 등 다양한 형태의 데이터를 키로 지정할 수 있다. 그리고 객체는 순서가 없는 반면 map은 insertion order가 있다.

const a = new Map()
const b = new Set()

https://javascript.info/map-set

081. Exercise. Implement A Hash Table

Private property

_hash? it is a kind of meaning-less property such as ‘You better not use this’ to other developers.

참고할 것들

https://javascript.info/private-protected-properties-methods

https://stackoverflow.com/questions/22156326/private-properties-in-javascript-es6-classes

BigO

hashTable의 bigO는 O(1) 또는 O(n)인데, 이번 경우에는 해시 테이블의 사이즈, 즉 메모리의 사이즈가 2로 매우 작기 때문에 O(1)라고 보면 된다.

Template

// HashTable Challenge : add set, get methods

class HashTable {
	constructor(size){
		// set memory size
		this.data = new Array(size);
		// 		[['grapes', 10000]]
	}
	
	//	hash function
	_hash(key) {
		let hash = 0;
		for (let i = 0; i < key.length; i++) {
			hash = (hash + key.charCodeAt(i) * i) % this.data.length
		}
		return hash;
	}
	

}

const myHashTable = new HashTable(50);
myHashTable.set('grapes', 10000);
myHashTable.get('grapes');

Solution

building Set method

// HashTable Challenge : add set, get methods

class HashTable {
	constructor(size){
		// set memory size
		this.data = new Array(size);
		// 		[['grapes', 10000]]
	}

	// hash function
	_hash(key) {
		let hash = 0;
		for (let i = 0; i < key.length; i++) {
			hash = (hash + key.charCodeAt(i) * i) % this.data.length
		}
		return hash;
	}
	
	set(key, value) {
		let address = this._hash(key) // 23 in case of 'grapes'
		
		if(!this.data[address]) {
			// if the address is empty, create []
			this.data[address] = [];
		} 
		// collision or not, anyway push
		this.data[address].push([key, value])
		
		return this.data;
	}
}


const myHashTable = new HashTable(2);

console.log(myHashTable.set('grapes', 10000))
// [undefined, [["grapes", 10000]]]

console.log(myHashTable.set('apples', 30))
// [undefined, [["grapes", 10000], ["apples", 30]]]

Building Get method

// HashTable Challenge : add set, get methods

class HashTable {
	constructor(size){
		// set memory size
		this.data = new Array(size);
		// 		[['grapes', 10000]]
	}

	// hash function : O(1) just quick loop so not O(n)
	_hash(key) {
		let hash = 0;
		for (let i = 0; i < key.length; i++) {
			hash = (hash + key.charCodeAt(i) * i) % this.data.length
		}
		return hash;
	}
	
	// 	set method : O(1) just pushing
	set(key, value) {
		let address = this._hash(key) // 23 in case of 'grapes'
		
		if(!this.data[address]) {
			// if the address is empty, create []
			this.data[address] = [];
		} 
		// collision or not, anyway push
		this.data[address].push([key, value])
		
		return this.data;
	}
	
	// 	get method : O(1) or O(n) depending on 1)size and 2)collisions
	// 	- In this case O(1)
	get(key) {
		let address = this._hash(key);
		const currentBucket = this.data[address];
		
		// If there is something
		if(currentBucket) {
				for(let i = 0; i < currentBucket.length; i++) {
					if (currentBucket[i][0] === key) {
						return currentBucket[i][1];
					}
				}
		}
		// There is nothing? return undefined
		return undefined
	}
}

const myHashTable = new HashTable(2);

console.log(myHashTable.set('grapes', 10000))
// [undefined, [["grapes", 10000]]]

console.log(myHashTable.set('apples', 30))
// [undefined, [["grapes", 10000], ["apples", 30]]]

console.log(myHashTable.get('grapes')) // 10000
console.log(myHashTable.get('apples')) // 30

083. keys()

keys() 메소드는 hash table의 모든 키를 출력해주는데, 이를 구현해보자.

// HashTable Challenge : add set, get methods
 
class HashTable {
 constructor(size) {
   // set memory size
   this.data = new Array(size);
   //      [['grapes', 10000]]
 }
 
 // hash function : O(1) just quick loop so not O(n)
 _hash(key) {
   let hash = 0;
   for (let i = 0; i < key.length; i++) {
     hash = (hash + key.charCodeAt(i) * i) % this.data.length;
   }
   return hash;
 }
 
 //    set method : O(1) just pushing
 set(key, value) {
   let address = this._hash(key); // 23 in case of 'grapes'
 
   if (!this.data[address]) {
     // if the address is empty, create []
     this.data[address] = [];
   }
   // collision or not, anyway push
   this.data[address].push([key, value]);
 
   return this.data;
 }
 
 //    get method : O(1) or O(n) depending on 1)size and 2)collisions
 //    - In this case O(1)
 get(key) {
   let address = this._hash(key);
   const currentBucket = this.data[address];
 
   // If there is something
   if (currentBucket) {
     for (let i = 0; i < currentBucket.length; i++) {
       if (currentBucket[i][0] === key) {
         return currentBucket[i][1];
       }
     }
   }
   // There is nothing? return undefined
   return undefined;
 }
 
 //    keys() method :  loop over n times
 //    in case of new HashTable(50) not (2)
 keys() {
   const keysArray = [];
   for (let i = 0; i < this.data.length; i++) {
     // if there is something
     if (this.data[i]) {
       keysArray.push(this.data[i][0][0]);
     }
   }
   return keysArray;
 }
}
 
const myHashTable = new HashTable(2);
 
console.log(myHashTable.set("grapes", 10000));
// [undefined, [["grapes", 10000]]]
 
console.log(myHashTable.set("apples", 30));
// [undefined, [["grapes", 10000], ["apples", 30]]]
 
console.log(myHashTable.get("grapes")); // 10000
console.log(myHashTable.get("apples")); // 30
 
console.log(myHashTable.keys());
 
// Another solution for key()
 
// keys() {
//     if (!this.data.length) {
//       return undefined
//     }
//     let result = []
//     // loop through all the elements
//     for (let i = 0; i < this.data.length; i++) {
//         // if it's not an empty memory cell
//         if (this.data[i] && this.data[i].length) {
//           // but also loop through all the potential collisions
//           if (this.data.length > 1) {
//             for (let j = 0; j < this.data[i].length; j++) {
//               result.push(this.data[i][j][0])
//             }
//           } else {
//             result.push(this.data[i][0])
//           }
//         }
//     }
//     return result;
//   }

085. Hash Tables VS Array

methods	Arrays	Hash Tables
search	O(n)	O(1)
lookup	O(1)	O(1) or O(n)
insert	O(n)	O(1)
delete	O(n)	O(1)
push	O(1)	-
features
in order	yes	no

*Hash Tables have no orders.

086. Hash Tables Exercise: First Recurring Character(시공간 복잡도와 순서 문제)

My solution

// Google Question
// Find the element that repeat first in array

const test1 = [2, 5, 1, 2, 3, 5, 1, 2, 4] // 2
const test2 = [2, 1, 1, 2, 3, 5, 1, 2, 4] // 1
const test3 = [2, 3, 4, 5] // undefined

function findRepeat(test) {
	const memory = new Array(test.length)
	
	for(let i = 0; i < test.length; i++) {
		if(!memory[test[i]]) {
			memory[test[i]] = test[i]
		} else {
			return test[i];
		}
	}
	return undefined
}

console.log(findRepeat(test3))

Solution 1 : O(n^2) and wrong

// Solution 1 : O(n^2)
function firstRecurringCharacter(input) {
	for (let i = 0; i < input.length; i++) {
		for (let j = i + 1; j < input.length; j++) {
			if (input[i] === input[j]) {
				return input[i];
			}
		}
	}
	return undefined;
}

Solution 2 with Hash Table: O(n)

// Solution 2 with Hash Table: O(n)
function firstRecurringCharacter2(input) {
	let map = {};
	
	for (let i = 0; i < input.length; i++) {
		if(map[input[i]] !== undefined) {
			return input[i]
		} else {
			map[input[i]] = i
		}
	}
	return undefined;
}
console.log(firstRecurringCharacter2(test1))

공간 복잡도와 시간 복잡도 비교

Solution1이 시간 복잡도가 O(n^2)으로 더 높긴 하지만 메모리에 저장하는 것은 없기 때문에 공간 복잡도는 낮다. 반면 Solution2는 시간 복잡도가 O(n)으로 더 빠르지만, 최악의 경우 객체에 모든 input 데이터를 저장하게 되어서 공간 복잡도가 높아질 가능성이 있다. 빠르게 찾을 경우, 공간 복잡도가 낮아질 가능성이 높다.

공간 복잡도 : Solution1 < Solution2

시간 복잡도 : Solution1 > Solution2

Solution1의 또 다른 순서 문제

Solution1의 경우 i, j 반복문으로 j를 먼저 돌린 뒤에 다음 아이템인 i를 고려한다는 문제가 있다. 무슨 말이냐면

[1, 2, 2, 1]의 경우, 2가 답으로 나와야 하지만 결과 값은 1이 나온다. 왜냐하면 1-2, 1-2, 1-1, 순으로 비교하면서 1-1를 찾게 되고 결국 결과는 1이 된다. 따라서 Solution1의 문제는 순서상 문제가 생겨서 답이 틀릴 가능성이 있다. 그래서 이 솔루션은 틀린 솔루션이 될 수 있다.

파이썬 dict, lists 관련 아티클

https://softwaremaniacs.org/blog/2020/02/05/dicts-ordered/en/

728x90

저작자표시

'Research > Data structure & algorithm' 카테고리의 다른 글

s10. Data Structure: Trees (0)	2022.11.29
Data Structure: Stacks + Queues (0)	2022.11.28
Data Structure: Arrays (0)	2022.11.24
Data Structure: Introduction (0)	2022.11.24
Big O의 개념, 유형, 계산 원칙 그리고 의미 (0)	2022.11.23

Programmer Way

Data Structure: Hash Tables

077. Hash Tables Introduction

What is Hash Tables?

Pros and Conds?

Pros

Cons

078. Hash Function

Hash Function?

Features

Performance

079. Hash Collisions

BigO

What is Hash Collision?

resolution for Hash Collision?

080. Hash Tables In Different Languages

081. Exercise. Implement A Hash Table

Private property

BigO

Template

Solution

building Set method

Building Get method

083. keys()

085. Hash Tables VS Array

086. Hash Tables Exercise: First Recurring Character(시공간 복잡도와 순서 문제)

My solution

Solution 1 : O(n^2) and wrong

Solution 2 with Hash Table: O(n)

공간 복잡도와 시간 복잡도 비교

Solution1의 또 다른 순서 문제

'Research > Data structure & algorithm' 카테고리의 다른 글

댓글

티스토리툴바

Data Structure: Hash Tables

077. Hash Tables Introduction

What is Hash Tables?

Pros and Conds?

Pros

Cons

078. Hash Function

Hash Function?

Features

Performance

079. Hash Collisions

BigO

What is Hash Collision?

resolution for Hash Collision?

080. Hash Tables In Different Languages

081. Exercise. Implement A Hash Table

Private property

BigO

Template

Solution

building Set method

Building Get method

083. keys()

085. Hash Tables VS Array

086. Hash Tables Exercise: First Recurring Character(시공간 복잡도와 순서 문제)

My solution

Solution 1 : O(n^2) and wrong

Solution 2 with Hash Table: O(n)

공간 복잡도와 시간 복잡도 비교

Solution1의 또 다른 순서 문제

'Research > Data structure & algorithm' 카테고리의 다른 글

관련글

댓글

티스토리툴바