TIL #4 220130

Subeeen·2022년 1월 30일
0

Today I Learned

목록 보기
4/18
post-thumbnail

오늘 배운 자료구조 HashTable에 대해 적어보려 한다.

해쉬 테이블

  • Key에 Value를 매핑할 수 있는 데이터 구조
  • 해쉬 함수로 배열에 키에 대한 데이터를 저장할 수 있는 주소(인덱스 번호) 를 계산
  • Key 를 통해 바로 데이터가 저장되어있는 주소를 알 수 있으므로, 저장 및 탐색 속도가 빠르다
  • 미리 해쉬 함수가 생성할 수 있는 주소(인덱스 번호)에 대한 공간을 배열로 할당한 후, 키에 따른 데이터 저장 및 탐색 지원

간단한 해쉬 함수

String name = "Donuts";
(int)(name.charAt(0)) % 20 //8

Key가 문자열일 때, 맨 앞글자를 숫자로 변환해 Division 기법을 사용하여 Key에 대한 주소(인덱스 번호)계산.

  • Division 기법 : 나누기를 통해 나머지 값을 사용하는 기법

해쉬테이블의 장단점과 용도

장점

  • 데이터 저장/읽기 속도가 빠르다(검색 속도가 빠르다)
  • 해쉬는 키에 대한 데이터가 있는지 중복 확인이 쉽다

단점

  • 일반적으로 저장공간이 좀더 많이 필요하다
  • 여러 키에 해당하는 주소가 동일할 경우 충돌(Collision)을 해결하기 위한 별도 자료구조가 필요하다

용도

  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현시(중복 확인이 쉽다)

생각해보기

Q. 원하는 요소를 찾을 때, 연결 리스트와 해시의 시간 복잡도?
A. 연결 리스트는 O(n), 해시는 O(1)

Q. 해시 함수를 작성할 때, 코드를 새로 실행하면 객체가 같더라도 다른 값이 나올 수 있다. 왜?
A. 객체의 hashcod 함수는 객체의 (힙)메모리 상의 주소값을 반환한다. 때문에 같은 객체이더라도 코드가 새로 실행될 때 마다 메모리 주소값이 변경되어 다른 값을 반환하게 된다. Object 클래스의 toString, equals, hashCode와 같은 메소드들은 오버라이딩을 하지 않으면 기본적으로 메모리 위치를 기반으로 코드가 실행된다.

Q. 해쉬 충돌을 방지하기 위해 해시의 크기를 최적화하는 방법
A.
1. 해시의 크기를 홀수로 설정하여 % 연산자를 사용했을 때 다양한 결과가 나오게 한다.
2. 해시의 크기를 소수로 설정하여 나머지가 다양한 숫자가 나오게 한다.

profile
백엔드 개발 공부 중!

0개의 댓글