[자료구조] 해시 테이블

❓ 해시 테이블이란

---

• 원소의 인덱스에 대한 사전 지식 없이 직접 접근을 제공하려고 시도하는 자료 구조
• "해시" = 원소들이 아무런 순서 없이 마구 뒤섞여 있다는 사실 반영
• 정렬하지 않고서도 더 좋은 성능
• 해시 함수를 가진 키 테이블

 

 

❓ 테이블과 레코드

---

• 레코드
  : 여러 개의 컴포넌트를 가진 복합적인 자료 구조
  : 외부 디스크 상에 데이터를 저장하기 위해 사용
  
  
• 키 레코드
  : 키와 값이라는 이름을 가진 객체의 순서 쌍
  연산)
  1. Initialize: 주어진 키와 주어진 값을 가지는 키 보유 레코드를 생성
  2. Key: 이 레코드의 키 객체를 리턴
  3. Value: 이 레코드의 값 객체를 리턴
  4. Update x: 이 레코드의 값 객체를 주어진 값 객체로 대체
  
  
• 테이블
  : 동일 타입의 레코드의 집합
  
  
• 키 테이블
  : 테이블에 저장된 레코드 전체에 대해서 값이 유일한 키 필드라는 특별한 필드 하나를
  레코드 타입이 포함하는 테이블

 

❓ Map

---

• 유일한 키를 갖는 키 보유 레코드의 컬렉션
• 연산)
  1. Initialize: 공백 맵을 생성
  2. Search: 주어진 키에 대해 테이블에서 그 키를 가진 레코드를 탐색. 발견시 그 값을 리턴. 그렇지 않으면 null을 리턴
  3. Insert/Update: 주어진 레코드에 대해 테이블에서 그 키를 가진 레코드를 탐색. 발견시 그 테이블 레코드의 값을 주어진 레코드의 값으로 대체하고 대체된 값을 리턴. 그렇지 않으면 주어진 레코드를 테이블에 삽입
  4. Delete: 주어진 키에 대해 테이블에서 그 키를 가진 레코드를 탐색. 발견시 해당 레코드를 테이블에서 삭제하고 그 값을 리턴. 그렇지 않으면 null을 리턴
  5. Count: 테이블의 레코드 수를 리턴

 

 

 

❓ 재해싱

---

• HashTable 클래스를 만들기 위한 개선안은 오버플로우 문제 해결하는 것 
  -> 솔루션: 더 큰 배열을 사용하여 테이블을 재구축 하는 것