Hash table

hash table 구현 방법

-Array list로 구현 ( 충돌시 Open addressing 방법으로 해결)

-Array list와 Linked list로 구현( 충돌시 Seperate chaining으로 해결)

 

해쉬 테이블

- 빠른 탐색을 위해서 자료구조를 key-value 쌍의 데이터로 입력을 받는다.

- 저장, 삭제, 검새개의 시간복잡도는 모두 O(1) 이다.

 

Direct-address Table

- index가 key값이 되는 테이블

index    value

 0            짱구

 1            맹구

 2            노진구

 3             백구

위에처럼 index가 key가 된다.

- 만약 학번을 key로 받고 싶다고 가정해보자. 그럼 엄청나게 큰 인덱스가 될것이다.

 학번이 202311223이면 앞에있는 많은 메모리가 낭비가 된다.

 

Hash table

- Direct-address Table의 문제점을 해결하기 위해 나왔다.

- 곧 바로 index로 사용하는게 아니라 한번 hachFunction함수(hashFunction은 우리가 구현하는게 아니라 이미 언어에 잘 구현된 hashFunctiono이 있음)를 이용해 가공을 거쳐서 key로 사용한다.

 

예를들어 key 값이 123,234, 432 가 있다면 각각 9로 나눈 나머지를 key값으로 사용하는거다.

이렇게 하면 어떤 값이든 0~8이내의 숫자만 나와서 메모리 낭비를 피할 수있다.

하지만 여기서 문제가 있다. 9로 나눠서 나온값을 key로 사용하면 충돌이 일어날 수 있다.

13, 22가 각각 9로 나눠지면 둘다 나머지는 4가 됨으로 같은 key 값을 가지게 되어 충돌이 일어난다.

이러한 충돌을 해결하는 방법으로 Open addressing 과 Seperate Chaining을 사용한다.

 

Dictionary

-파이썬에서는 이 Hash table이 Dictionary라는 자료구조로 되어있다.

-Dictionary는 특정 데이터를 찾는데 시간복잡도 O(1)을 가진다.(메모리를 사용해서 시간복잡도를 줄임)

-{Key1:Value1, Key2:Value2, Key3:Value3, ...}

 

이제 이 Dictionary를 활용한 알고리즘 문제를 풀어보자

 

'''
문제1) 정수가 저장된 nums이 주어졌을때 원소중 두 숫자를 더해서 target이 될 수 있으면 True
불가능하면 False를 반환하시오. 같은 원소를 두번 사용할 수 없다.
'''


def findTarget(list, target):
    dictionary = {}  # dictionary 초기화
    for k in list:  # dictionary에 입력된 list 값 넣기
        dictionary[k] = 1

    for k2 in list:
        value = target - k2
        if value == k2:  # 같은 원소를 두번 사용하지 못하니 False
            return False
        if value in dictionary:  # k2에 더해서 target이 되는 숫자가 dictionary에 있는 경우
            return True

    return False


print(findTarget([2, 3, 14, 21, 23, 7, 5, 34], 35))  # True


'''
문제 2)
정렬되어 있지 않은 정수형 배열 nums가 주어졌다. nums 원소를 가지고 만들 수 있는 가장 긴 연속된 수의 갯수는
몇개인지 반환하시오.
'''


def getMaxNumLength(list):
    dic = {}
    length = 1
    maxLength = 1

    for k in list:
        dic[k] = k

    if len(list) == 0:
        return 0
    for k2 in list:
        if k2 - 1 not in dic:
            next = k2 + 1
            while next in dic:
                length += 1
                next += 1

            if maxLength < length:
                maxLength = length
            length = 1

    return maxLength


print(getMaxNumLength([5, 4, 2, 1, 56, 34, 33, 32, 31, 35])) # 5