TIL(03.20/ 1W 5D/ Fri)

Seokhwan Yi·2020년 3월 24일

TIL

목록 보기

4/9

Data-Structure Series Linked List, Hash Table

Linked List

열결된 리스트(목록)
이 그림이 좀 더 이해하기 쉬웠다.

노드에 정수 값과 다음 노드에 대한 링크(next)라는 두개의 필드가 포함된 단일 링크 목록이다.

Array List vs. Linked List

첫 회사는 한층에 있어야 된다는 규정이 있어서 사무실이 좁아지면 더 이상 새로운 직원을 뽑기가 힘들다. 더 많은 공간이 필요하면 이사를 해야한다. 하지만, 두번째 회사는 한 건물 내에서 이 회사가 임대한 사무실이 여기저기 떨어져있다. 덕분에 직원이 늘어도 걱정이 없다. 건물에 비어있는 아무데나 임대해서 들어가면 되는데 방문자가 사무실을 찾기가 너무 비효율적이다. 왜? 3번째 방에 가고 싶다면, 우선 첫번째 화살표의 사무실을 찾아가서 다음 사무실이 어딘지 물어야 하고, 또 물어본 사무실에 가서 또 묻고를 찾을 때까지 반복한다. 그래서 linked list에선 몇 번째 element를 찾는 것이 느리다. 반면에, array list는 element가 같은 곳에 모여있기에, 3번째 자리로 가고 싶다면 한번에 3번째 방으로 갈 수 있다.

그래서 Linked List의 구조와 Pseudo code?

총 4개의 노드가 있다.
객체 지향에선 node를 객체로 표현한다.
저장되는 첫번째 값 10을 Datafield에 저장하고, 다음 노드가 무엇인지 Link field에 저장해준다. 그래서 첫번째 노드가 무엇인지 모르면 안돌아가기에 HEAD에 첫번째 노드를 적어준다. 이역시 변수이다.

Hash Table

사전적의미: 잘게 썰다.
Hash Potato (감자로 만들었지만 잘게 다져 감자인지 모르는...) 가 생각났다. 그렇다면 데이터를 입력 받아서 다른 형태로 데이터를 얻는다 정도로 생각이든다.
해싱: 해시함수와 해시 테이블을 이용한 키값의 탑색, 제거
해시 함수 : 식별자 x의 해시 테이블 내 위치 결정을 위한 수학적 함수
해시 주쇠 해시 함수에 의해 결정된 식별자의 저장 주소

동작 방식?

도대체 어찌 동작하는가? 간단히 생각하면 내가 찾고 싶은 친구의 전화번호가있는데 Hash 함수라는 곳에 친구의 이름을 적으면 해쉬함수를 통해 인덱스(해시 코드)를 참조하여 버킷에 저장되어있는 번호를 알려주는데 이 해시 함수에 의해 저장 위치를 직접 계산 할 수 있는 테이블 구조를 Hash Table이라 부른다.

Collision(충돌)

서로 다른 key를 가지고 있는데, 해시함수로부터 리턴된 해시주소가 동일할때!

크기가 12개월로 1년의 크기의 해시테이블이 있다고 하면, 
한 결혼식장(버킷)에 하루에 20명의 커플이 날짜를 잡고 이 날짜를 각각 테이블에 저장하려할때, 20명의 커플이 원하는 '달'이 모두 다르면 골고루 해시 테이블에 들어가겠지만, 날씨좋고 볕좋은 좋은 달들을 같이 선택한 커플들이 있다. 이때 이 커플들을 한 버킷에 넣게 되는데 이때 '충돌' 이라 한다.

해시 테이블의 Bucket안에는 여러 개의 slot이 있어 충돌이 생겨도 값을 저장할 수 있지만, slot의 개수가 정해져있기 때문에 주어진 slot이 다 차버리면 저장을 못하게 된다. 이때 overflow 가 발생 한다.

Overflow

"key값이 모든 슬롯에 꽉 차 Bucket에 매핑됐다 라고 표현"
만약 앞과의 상황(버킷 안의 슬롯이 모두 찬 경우) 그 버킷에 key를 할당하면 overflow가 발생한다고 했다. 만약 버킷당 slot수를 1개로 정해 놓으면 collision, overflow가 동시에 일어난다.
따라서 좋은 해시 함수는 해시 테이블에 적절히 데이터들을 분산시켜주는 것이다.

해결 방법?

Chaining, LinkedList 이용, Linear Probing, 선형탐사 등이 있다.
1. 해쉬테이블은 25%에서 75% 사이에 차있을때 가장 효과적으로 운영이 된다.

그래서 75%가 넘어간다면 사이즈를 두배로 넓혀준다. * 25% 이하이면 사이즈를 작게 해준다.
자료 리사이즈 시켜주기.

2.말하지 않은 것들

해쉬 테이블이 커지면 해슁을 다시 해줘야한다.
해쉬함수가 너무 별로여서 모든 키들이 같은 버킷에 들어가게 되었다. 그러면 서칭을 O(n)의 타임컴플렉서티로 하기 때문에 findtimecomplexity가 발생하게 된다.

PseudoCode

해쉬테이블을 생성하는 함수를 만드는데 이때 limit값8과 스토리지에 저장할 제한된 배열을 만들어준다.>
해쉬테이블에서 key값으로 index를 구해서 value를 넣는 insert함수를 만들어준다.>
해쉬테이블에서 key값으로 value를 찾아 반환해주는 함수. get함수를 통해 index를 가져온다.>
해쉬테이블에서 key로 value를 찾아 삭제하는 함수. each함수를 이용해서 찾을 값을 i번째 index가 같으면 undefined를 주자.>