Hash Table

1. Hash Table이란

해시 테이블은 (Key,value)를 기반으로 데이터를 저장하는 자료구조중 하나이다.
해시테이블은 아래의 그림과 같이 Key값을 Hash 함수를 이용하여 고유한 index값으로 변환하고, 이 index에 해당되는 배열(bucket)의 위치에 저장한다. 이런한 구조로 인해 Key값에 Hash 함수를 수행하기만 하면 value값이 저장되어있는 Index를 얻는것이 가능하기 때문에 탐색에 O(1)의 시간복잡도가 소요된다.

2. Hash Functions

Hash 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
Hash Table에서는 Hash 함수를 이용하여 Key에서 부터 고유한 index를 얻는다. 아래에는 간단한 Hash 함수들을 나열해 보았다.

• Division Method : 가장 간단한 Hash함수중 하나로 Key값을 Bucket의 사이즈로 나누어서 계산한다.
• Digit Folding : Key의 문자를 ASCII 코드로 바꿔 합한 데이터를 테이블 주소로 사용한다.
• Multiplication Method :

3. Hash Collapse

Hash 함수에 서로 다른 입력값을 넣었지만 같은 출력값이 나올경우 발생할 수 있는 상황을 말한다. 이러한 상황이 발생할때 해결방법으로 아래와같은 충돌 처리기법이 존재한다.

3.1 충돌 처리 기법

• Open Hashging : 주소 밖의 메모리에 저장
  • Chaining : 충돌이 발생하면 해당 주소에 linked list 이용해서 연결해 저장하는 방법
    • 데이터를 찾을시에 순차탐색을 해야하는 단점이 생김
• Close hashing(Open Addressing) : 테이블 내의 새로운 주소를 탐색하여 데이터를 입력하는 방식
  • Linear probing : 충돌이 발생할때마다 고정값만큼 이동한 주소에 저장하는 방법
  • Quadratic probing : 충돌이 발생한 만큼의 제곱값을 폭으로 주소에 저장하는 방법
  • Double hashing : 해시된 값을 한번더 해싱하여 새로운 주소를 할당하는 방법

reference

http://www.laurentluce.com/posts/python-dictionary-implementation/

Array & ArrayList & LinkedList 의 특징

Array(배열)

• Array는 선언함과 동시에 크기를 함께 적어줘야하는 자료구조이다.
• Array를 선언하면서 특정 자료형과 배열의 크기를 함께 적어주면 특정 자료형이 들어갈 메모리공간을 미리 할당한다.
• 데이터를 삭제해도 공간이 남아있다.
• 장점
  • 미리 주소값(Index)을 할당하다보니 데이터검색이 빠르다.
• 단점
  • 선언한 크기 이상의 데이터를 가지는것은 불가능하기 때문에 데이터가 늘어나거나 하는 최대사이즈를 알수없는 상황에서 사용하기 부적합하다.
• ex) c, c++의 배열

ArrayList

• ArrayList는 크기가 정해져 있지 않다.
• 데이터에 순서가 Index형식으로 존재한다.
• 데이터를 중간에 추가하면 기존에 데이터는 Index의 변화가 일어난다. (뒤로 하나씩 밀리거나 당겨지거나)
• 장점
  • 배열과 같이 Index가 존재하기 때문에 데이터검색이 빠르다.
  • 데이터 검색에 $O(1)$의 시간복잡도
• 단점
  • 중간에 추가하면 기존 데이터의 Index에 변화가 일어나기 때문에 추가적인 연산이 필요하다.
  • 데이터 추가와 삭제에 $O(n)$의 시간복잡도

LinkedList

• 각 노드가 데이터와 포인터를 가지고 연결되어 있는 방식으로 데이터를 저장
• 한방향으로만 연결되거나, 양방향으로 연결, 순환구조로 연결 등의 여러가지 방식이 존재한다.
• 장점
  • 노드의 연결만 끊어주면 되기때문에 데이터의 추가 삭제가 간단함
  • 시간복잡도 $O(1)$
• 단점
  • 특정위치의 데이터를 알기 위해서 처음부터 탐색을 해야하기 때문에 시간이 소요됨
  • 시간복잡도 $O(n)$
• 추가 정보

링크드리스트

링크드 리스트는 각 노드가 데이터와 포인터를 가지고 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다

장점

• 원소 추가와 제거가 쉬움 : 시간복잡도 $O(1)$
• list의 크기를 가변적으로 사용가능

단점

• 탐색에는 효율이 좋지 않음 : 특정위치 탐색에 걸리는 시간복잡도 $O(n)$

결론

• 가변적으로 자주 변하는 데이터에 사용하면 좋다

종류

• 단일 연결 리스트 : 단방향으로 포인터가 연결된 리스트
• 이중 연결 리스트 : 양방향으로 포인터가 연결된 리스트
• 순환 연결 리스트 : Head와 Tail의 노드가 연결되어 순환구조를 가지는 리스트

구현

양방향 리스트로 구현해 보았다.

1. 노드
   • 데이터를 담을 노드를 구현

     1 2 3 4 5

     class Node: def __init__(self, Data): self.Data = Data self.prev = None self.next = None

2. 리스트
   • head와 tail은 더미데이터를 넣어주어서 고려할 사항을 줄여줌

     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

     class linked_list: def __init__(self): dummy = Node(None) self.head = dummy self.tail = dummy self.current = dummy def add(self, data): # 새로운 노드를 추가 newNode = Node(data) self.tail.next = newNode newNode.prev = self.tail self.tail = newNode self.current = newNode def delete(self): # 현재 활성화 노드를 삭제하고 리턴 next_node, prev_node = self.current.next, self.current.prev if next_node != None: next_node.prev = prev_node prev_node.next = next_node return self.current def delete_n(self, n): # n번째 노드를 삭제하고 리턴 current = self.head.next for _ in range(n-1): current = current.next def prev(self): # 활성화 노드를 prev로 이동 self.current = self.current.prev def next(self): # 활성화 노드를 next로 이동 self.current = self.current.next