data structure

# 자료구조란?

 

- 자료를 저장하는 구조

- ADT 에서 자료 저장 방법과 연산방법을 자세히 구현

- 잘 사용한 다는 것은? 구현하고자 하는 목적에 맞는 자료구조 사용해 효율적인 성능으로 구현

 

## 추상적 자료형 (Abstract Data Type)

 

자료를 담는 방법과 자료에 대한 연산에 대한 정의가 담긴 것. 구현방법은 정의되어있지 않다.

 

## 리스트라는 ADT를 구현한 자료구조 ?

 

- 배열

- 연결 리스트

- 서로 장점과 단점이 일치함..

 

# 해시테이블

 

- Key-Value Store를 구현하기 위해 생긴 개념

- 각각 data 고유한 key에 대응하도록 저장

 

## 정의

 

- 배열에 value를 저장하고, 배열의 index를 key로 이용하는 방식으로 구현하자

- put : key value쌍 입력

- get : key, value 조회

 

```

db = keyvalueStore()

 

db.put(2,7)

#2라는 키에 7 넣기

 

db.get(4)

#4번키가 갖고있는 게 무엇인지

```

 

## 배열의 index를 key로 사용하는 방법

 

- 장점 : 자료의 쓰기, 읽기 연산이 빠르다

- 단점 : 자료가 없다는 것을 표현하는 게 쉽지 않다. 공간이 낭비될 수 있다.

 

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

 

- key를 저장하는 배열과 value를 저장하는 배열, 두 개의 배열을 사용해 저장

- 같은 인덱스끼리 key,value인, 2개의 배열(myKey, myValue)을 만든다

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

- 단점 : 자료의 읽기(조회), 쓰기(입력)연산이 느리다. (순차탐색 해야하므로)

 

# 해시(Hash)

 

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

- 변환하는 과정 자체를 hashing, 변환된 값을 hash value라고도 부름

- 해시알고리즘의 대표적인 예시 ) SHA-256

- Python 내장함수

    - hash()를 이용하여 임의의 값의 해시값(정수)를 알 수 있다.

    - 보안을 이유로 프로그램을 실행할 때마다 반환값이 달라진다.

    - 앞 4자리만 같고, 그 뒤에 무작위 정수값

- hash 충돌

    - 인덱스가 겹치게 되는 문제

    - 비둘기집의 원리 : n개의 비둘기 집에 (n+1)마리의 비둘기를 한 집에 한 마리씩 넣는 것은 불가능하다는 원리를 말한다.

        - 비둘기가 최대 1마리씩 들어있는 비둘기집이 n개 있다면, 전체 비둘기 집에는 비둘기가 많아야 n마리 존재한다. 따라서 (n+1)마리의 비둘기를 n개의 비둘기 집에 한마리씩 넣는 것은 불가능

    - 연락처에 있는 사람 366명의 생일을 올해 달력에 적으려고 할 때, 윤년이 아니고 2월 29일이 생일인 사람이 없다면 한 날짜에 두 사람의 이름을 적어야 하는 경우가 반드시 생김

    -> 충돌 필연적으로 발생

- hash 충돌 해결하는 방법

    - 개별 chaining

        - key-value store의 각 인덱스를 '연결리스트'로 만들어서 동일한 인덱스의 값들을 연결하는 방법

        - 동일한 index를 갖는 자료를 서로 연결

    - 오픈 addressing

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

        - 모든 원소가 자신의 해시값과 일치하는 인덱스에 저장된다는 보장은 없음

        - 선형 탐사 방식 : 다음 인덱스부터 탐색하여 가장 가까운 빈 공간을 찾는 방법

    - Python에서는 딕셔너리의 해시 값 충돌 발생 시, 오픈 어드레싱 방식으로 해결한다.