TIL 221115

1. 자료구조

1) 해시 테이블

[1] 해시 테이블?

• 해시테이블은 key-value 페어를 저장한다.
• 기본적으로 array와 유사하지만, 순서가 정의되지 않는다.
• 값에 접근하거나, 추가하거나, 제거하는데 소요되는 시간이 매우 짧다.
• Python에서는 Dictionaries, JavaScript에서는 Objects와 Maps가 있다.
  • JS의 Objects에서는 String만을 key로 사용할 수 있다.

[2] 해시 함수

• 임의의 크기를 가지는 데이터를 입력하면 정해진 크기의 데이터를 출력하는 함수.
• 단방향 함수기 때문에 출력값을 보고 입력값을 유추하기 힘듬.
• 여기서 말하는 해시 함수는, 암소기술을 사용한 보안 해시 함수가 아니다.

hash("A") # 7219307595457212775
hash("a") # 2798505296300802053
hash("jjfioewniqnvinqiowejfioqf") # -2027044758203323713

[3] 좋은 해시 함수에 필요한 것

• 빠른 처리속도.
• 일관된 방식으로 분배를 해서 다른 것들과 겹치지 않게 해야 함.
• 특정 입력값을 입력할 때마다 같은 출력값이 나와야 한다.
  아래는 아주 원시적인 스트링을 키로 받는 해시 함수

def hash(key,array_len):
    total = 0
    prime_num = 31
    for i in range(len(key) or 100):
        value = ord(key[i]) - 96
        total = (total * prime_num + value) % array_len
    return total

[4] 해시 테이블의 충돌을 해결하는 체이닝, 선형 조사법

• 체이닝

  • 같은 자리에 배열이나 링크드리스트를 활용해 이중 데이터 구조를 사용.
    

• 선형 조사법

  • 충돌이 일어나면, (주로) 앞쪽에 있는 빈 공간에 데이터를 저장.
    

2) (이진) (검색) 트리

[1] 트리

• 링크드 리스트처럼 노드로 이루어진 데이터 구조.
• 차이점으로는 노드간에 부모-자식 관계가 있다.
  
• 리스트는 선형 구조, 트리는 비선형 구조.
• Root라는 가장 꼭대기에 있는 노드가 있어야 한다. Root는 트리 내에서 유일하다.
• Child는 루트에서 멀어지는 방향으로 연결된 노드. 트리에서는 항상 수직방향으로 연결된다.
• Parent는 자식과 반대되는 개념이다.
• Siblings는 형제자매, 같은 Parent를 가지는 노드다.
• Leaf는 자식이 없는 노드다.
• Edge(간선)는 노드와 다른 노드의 연결이다.

[2] 이진 트리

• 모든 부모 노드는 최대 2개의 자식을 가진다.

[3] 이진 검색 트리

• 부모 노드의 왼쪽에 있는 모든 노드는 언제나 부모보다 작다.
• 부모 노드의 오른쪽에 있는 모든 노드는 언제나 부모보다 크다.