[자료구조] 자료구조란? 4일차 마무리 해시테이블
자료구조는 왜 공부해야하냐!!
: 프로그램의 의도에 맞는 자료구조를 사용하여 효율적인 성능으로 구현하기 위해
해시 테이블
: 각 데이터(value)를 고유한 key에 대응하도록 저장하는 개념
좌) key 10101 데려와라! (ex_1학년 1반 1번 학생은 누구냐!)
우) value 데려옴 (ex_ 이름 엘리스, 성적은 100…) / 각각의 고유한 겹치지 않는 key에 대해서 데이터를 묶어줌.
key가 정수이고 value 역시 정수인 Key-Value Store를 구현해보자
Key-Value쌍을 입력하는 연산은 put, 특정 Key의 Value를 조회하는 연산은 get이라고 정의
배열의 index를 key로 이용하기
- 배열에 value를 저장하고, 배열의 인덱스를 key로 이용하는 방식으로 구현해보자!
장점
- (운 좋으면) 자료의 쓰기 연산, 읽기 연산이 빠르다. (기존의 배열 안일 경우에)
단점
- “자료가 없다”를 표현하는 것이 쉽지 않다.
- 공간이 지나치게 낭비될 수 있다.
- put
: 2번 인덱스에 7을 넣음
2. get
: 4번 인덱스에 있는 배열 조회
⚠️ 문제점 ⚠️
배열의 크기를 벗어난 인덱스에 추가해야 하는 경우는??
: 인덱스를 100까지 늘린 후 2를 넣는건데 6에서 100까지 빈 공간이 생겨 비효율적임.
⚠️ 문제점 ⚠️
value가 없는 인덱스에 get을 하는 경우는??
: 존재하는지 아닌지 명확하게 구분할 수가 없음.
key와 value를 각각 배열에 저장하기
: key를 저장하는 배열과 value를 저장하는 배열, 두 개의 배열을 사용하여 저장하기.
장점
- 공간의 낭비가 없다.
- 자료가 없는 경우를 표현할 수 있다.
단점
- 자료의 읽기(조회), 쓰기(입력 등) 연산이 느리다.
- put
: 그냥 key 4에 value 8을 추가해주면 됨(빈 공간 안생김)
2. get
: 인덱스 2번의 요소가 4니까 인덱스 2번의 value값 8을 뱉음.
해시(hash)
: 임의의 데이터에 해시 함수를 이용하여 고정된 길이의 데이터(문자열 등)으로 변환하는 것.
: 변환하는 과정 자체를 해싱, 변환된 값을 해시 값 이라고도 부름.
: 파이썬의 hash()함수는 보안을 이유로 프로그램을 실행할 때마다 반환값이 달라짐.
해시 테이블 또는 딕셔너리
: 인덱스가 겹치게 되는 문제를 해시 충돌이라고 함.
좋은 해시 함수는 중복되는 해시 값이 최대한 없도록 해서 충돌 발생하지 않는 거지만
어쩔 수 없이 발생함.
해시 충돌 해결 방법 = 개별 체이닝
개별 체이닝
: key-Value Store의 각 인덱스를 ‘연결 리스트’로 만들어서 동일한 인덱스의 값들을 연결하는 방법
: 엘리스 값 뒤에 도도를 연결리스트로 연결
: 1번 키에 접근하면 첫번째로 엘리스 그 뒤를 따라가면 도도가 있음.
?? 도도를 찾고 싶다면? get(’dodo’)
해시 충돌 해결 방법 = 오픈 어드레싱
오픈 어드레싱
: 충돌이 발생했을 때 자료를 저장하기 위해 빈 공간을 탐색하는 방식
: 그래서 해시 값과 일치하지 않는 인덱스에 저장될 수 있음.
오픈 어드레싱 방법 중
- 가장 간단하고 대표적인 방법은 선형 탐사 방식
- 원래 인덱스의 다음 인덱스부터 탐색하여 가장 가까운 빈 공간을 찾음.