[자료구조] 자료구조란? 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로 이용하는 방식으로 구현해보자!

장점

• (운 좋으면) 자료의 쓰기 연산, 읽기 연산이 빠르다. (기존의 배열 안일 경우에)

단점

• “자료가 없다”를 표현하는 것이 쉽지 않다.
• 공간이 지나치게 낭비될 수 있다.

1. put

: 2번 인덱스에 7을 넣음

 

2. get

: 4번 인덱스에 있는 배열 조회

⚠️ 문제점 ⚠️

배열의 크기를 벗어난 인덱스에 추가해야 하는 경우는??

: 인덱스를 100까지 늘린 후 2를 넣는건데 6에서 100까지 빈 공간이 생겨 비효율적임.

⚠️ 문제점 ⚠️

value가 없는 인덱스에 get을 하는 경우는??

: 존재하는지 아닌지 명확하게 구분할 수가 없음.

 

key와 value를 각각 배열에 저장하기

: key를 저장하는 배열과 value를 저장하는 배열, 두 개의 배열을 사용하여 저장하기.

장점

• 공간의 낭비가 없다.
• 자료가 없는 경우를 표현할 수 있다.

단점

• 자료의 읽기(조회), 쓰기(입력 등) 연산이 느리다.

1. put

: 그냥 key 4에 value 8을 추가해주면 됨(빈 공간 안생김)

 

2. get

: 인덱스 2번의 요소가 4니까 인덱스 2번의 value값 8을 뱉음.

해시(hash)

: 임의의 데이터에 해시 함수를 이용하여 고정된 길이의 데이터(문자열 등)으로 변환하는 것.

: 변환하는 과정 자체를 해싱, 변환된 값을 해시 값 이라고도 부름.

: 파이썬의 hash()함수는 보안을 이유로 프로그램을 실행할 때마다 반환값이 달라짐.

해시 테이블 또는 딕셔너리

: 인덱스가 겹치게 되는 문제를 해시 충돌이라고 함.

좋은 해시 함수는 중복되는 해시 값이 최대한 없도록 해서 충돌 발생하지 않는 거지만

어쩔 수 없이 발생함.

 

 

해시 충돌 해결 방법 = 개별 체이닝

개별 체이닝

: key-Value Store의 각 인덱스를 ‘연결 리스트’로 만들어서 동일한 인덱스의 값들을 연결하는 방법

: 엘리스 값 뒤에 도도를 연결리스트로 연결

: 1번 키에 접근하면 첫번째로 엘리스 그 뒤를 따라가면 도도가 있음.

?? 도도를 찾고 싶다면? get(’dodo’)

 

 

해시 충돌 해결 방법 = 오픈 어드레싱

오픈 어드레싱

: 충돌이 발생했을 때 자료를 저장하기 위해 빈 공간을 탐색하는 방식

: 그래서 해시 값과 일치하지 않는 인덱스에 저장될 수 있음.

 

 

오픈 어드레싱 방법 중

• 가장 간단하고 대표적인 방법은 선형 탐사 방식
• 원래 인덱스의 다음 인덱스부터 탐색하여 가장 가까운 빈 공간을 찾음.
•