자바스크립트 12. 자료구조(Data Structure) - 해시테이블 (Hash Table)

자료구조 4번째 해시테이블을 기록해보자!

하 유럽가고 싶다. 왜 이사진을 올렸냐구요????그냥 헤시테이블이라길래 내가 가장좋아했던 테이블사진이라 올렸어요후 ... 여기는 영국 런던 Oxford Circus에 있는 The Breakfast Club입니다. 메뉴는 Full-monti였나..? 하.. 또 가고싶네

📕해시테이블(Hash Table)의 개념

해시 테이블(Hash Table)은 입력받은 키값을 해시함수에 돌려서 반환받은 해쉬코드는 배열의 인덱스로 데이터에 접근하는 자료구조 입니다.

사진을 보면 이해하기가 더 쉽다. 주어지는 key는 해시함수에 들어가게 된다. 해시 함수는 받은 키를 해쉬 코드로 바꾸어주는 역할을 한다. 그렇게 키는 해시 함수를 지나서 해시 코드가 된다. 해시 코드는 인덱스 처럼 저장소(bucket)에서 값을 찾고 접근을 할 수 있게 된다. 이때 접근, 삭제, 검색 등이 가능해진다.

---

👨🏻‍💻해시테이블 활용 예시

• 핸드폰 연락처 (이름 검색을 하면 -> 해당번호가 나온다)

• DNS 확인작업 (웹사이트 주소를 입력하면, 컴퓨터는 그 주소를 IP주소로 변환한다.)

• 웹사이트 비밀번호

---

📍해시테이블(Hash Table) 메소드

이번 코드스테이츠 스프린트에서 연결리스트 메소드를 구현한 것은 총4가지 이다.

• insert(key, value) - 주어진 키와 값을 저장합니다. 이미 해당 키가 저장이 되어있다면 값을 덮어 씌웁니다.

• retrieve(key) - 주어진 키에 해당하는 값을 반환합니다. 없다면 undefined를 반환합니다.

• remove(key) - 주어진 키에 해당하는 값을 삭제하고 값을 반환합니다. 없다면 undefined를 반환합니다.

• _resize(newLimit) - 해시 테이블의 스토리지 배열을 newLimit으로 리사이징 하는 함수입니다. 리사이징 후 저장되어 있던 값을 전부 다시 해싱해 주어야 합니다. 구현 후 Hash Table 내부에서 사용하면 됩니다.

---

🔥해시 충돌(Hash Collision)

먼저 메소드를 구현하기 전에 해시 충돌에 대해서 살펴보아야한다. 왜냐하면 주어지는 key의 값은 무한하지만, 인덱스는 유한하기 때문입니다. 그렇기 때문에 해기 함수는 한정된 인덱스에 값을 얼마나 골고루 잘 넣게 만드는지가 아주 중요합니다.

예를 들어 다음과 같은 '해시 함수'가 있다고 가정해 봅시다.

각각의 키들이 평화롭게 저장소에 들어가서 살포시 저장되어 있습니다. 그런데!!!!!! 54가 등장해 버립니다!!!!!!!

눈치 없이 등장한 54때문에 이전에 들어왔던 34는 굴러온 돌이 박힌돌 빼낸다고 '충돌'이 일어났습니다. 그렇다면 어떻게 해결 할 수 있는가?..?

1. Open addressing

- 다른 여분의 인덱스로 지정해주는 방법이 있습니다. 지금 4번 칸에 충돌이 일어났는데, 다음 칸이 5번이 비어있는지 확인해보고 비어 있다면 5번 자리에 저장하는 방법입니다.

 

- 아니면 해시 함수를 1개가 아닌 2개를 작성해서, 평소에는 기존의 해시 함수를 잘 쓰다가, 만약에 충돌이 발생하게 되면 두번째 해시함수를 실행시켜서 인덱스를 조정하게 됩니다.

2. Close addressing

충돌이 만약에 발생하면 다음 인덱스에 할당하는 것이 아니라, 그 저장소 안에 배열을 만듭니다. 즉 이차원 배열을 만들어서 값을 저장하는 방식입니다.

 

왼쪽이 open addressing 오른쪽이 close addressing

---

💻해시 함수 메서드 구현

이번 스프린트는 코드스테이츠에서 헬퍼 함수도 주었습니다! 해시 함수도 역시 주어 졌습니다!

class HashTable {
  constructor() {
    this._size = 0;
    this._limit = 8;
    this._storage = LimitedArray(this._limit);
  }

1.insert(key, value)

- 객체로 해서 만들기 위해서 빈객체를 하나 만들었습니다

- 키 값이 해시함수를 지나서 해시코드로 변경이 된 인덱스가 저장소에 없으면 해당하는 키와 값을 지정해주고, 만약에 있다면 덮어 씌우도록 함수를 작성했습니다.

- 그리고 값이 들어 왔기 때문에 사이즈를 수정해 줍니다.

 

2. retrieve(key) 

- 저장소에 해당하는 키값이 없다면(=== 이 연산자 활용) undefined를 반환하게 해주었고, 있으면 해당하는 값을 반환 시켰습니다.

 

3. remove(key)

- 저장소에서 해당하는 값을 변수를 지정해서 할당해 주고, 값을 삭제해 주었습니다.

- 그리고 사이즈를 수정해 주었습니다.

 

4. _resize(newLimit)

- 먼저 기존에 있었던 저장소를 다른 곳에 할당해서 미리 빼놓습니다.

- newLimit을 다시 지정해주고, 다시 기존의 값들을 해싱해서 저장소로 옮기도록 작성했습니다.

 

🖐🏻사이즈를 수정할 때는 resize함수를 실행 시켰습니다.

해시 테이블은 안에 있는 데이터가 25~75%정도 차 있을 때 가장 높은 효율을 내기 때문에 공간을 계속해서 저 사이로 유지 하는 것이 좋습니다. 그렇기 때문에 insert나 remove를 실행했을 때 저장공간이 25~75%정도를 유지하고 있는지 확인해주고 수정해 주어야합니다!

 

다음에도 계속해서 자료구조를 기록해보자!