지난 포스팅에서는 배열의 검색 알고리즘 중 하나인 Hash 검색에 대해 알아보았다. Hash 검색은 배열에 저장할 자료가 가지는 특수한 값을 key 값으로 선정하고, 그 key 값으로부터 추출한 Hash 값을 통해 배열에 저장할 index를 지정하는 방식이다. 그리고 Hash 검색을 이용하는 자료구조형은 Python의 Dictionary와 매우 유사하다.
Hash를 통해 index를 지정하는 과정에서, 서로 다른 key 값이 배열 내의 같은 index를 지정받을 수 있다. 이렇게 될 경우, 나중에 저장된 값이 이전에 저장된 값을 지워버리기 때문에 정보의 저장이라는 측면에서 문제가 발생하게 된다. 이렇게 Hash 검색 알고리즘과 자료구조에서, 저장할 배열의 위치가 서로 공유되는 현상을 Hash 충돌이라고 한다.(실제 예는 이전 포스팅의 내용을 참고해주시면 된다. 위의 링크를 눌러 확인바란다).
따라서 Hash 충돌이 발생할 경우, 이전에 존재하던 값도 손상없이 저장할 수 있는 알고리즘이 만들어졌다. 바로 체이닝(Chaining)이라고 불리는 연결 리스트를 사용하는 알고리즘과, 배열 내의 빈 index를 찾아 값을 저장하는 개방 주소법(Open Addressing)이라는 방법이다.
이번 포스팅에서는 Hash 충돌을 해결하는 두 알고리즘 중 하나인 체이닝에 대해 알아보려 한다.
1. 체이닝(Chaining)
Chaining은 동일한 Hash 값을 가지는 정보를 배열 내 동일한 list에 저장하되, 배열 내에 저장된 둘 이상의 자료를 연결 리스트(Linked List)로 연결하는 방식이다. 연결 리스트는 여러 값이 마치 비엔나 소시지마냥 줄줄 늘여진 모양새인데, 각각의 값은 순서상 자신의 뒤에 위치한 값의 메모리 주소를 Pointer로 가리키고 있기 때문이다. 말로는 설명이 어려우니 아래의 그림을 참고하자.
만약 동일한 Hash 값을 가진 값들이 하나의 index를 공유하게 될 경우, 가장 마지막에 추가된 값은 배열의 index의 Pointer에 의해 참조되게 된다. 그 이전에 동일 index로 저장된 값은 가장 마지막에 추가된 값의 Pointer에 의해 참조된다.
따라서 Chaining을 위한 자료구조는 이전에 저장되어 있는 값, 즉 Pointer가 가리키고 있는 값을 참조할 수 있도록 별도의 변수를 포함해주어야 한다. 그렇기 때문에 배열에 저장되는 값의 자료형은 단순 문자열이 아니라, 별도로 정의된 구조체, 즉 Class가 되어야 한다.
2. Chaining 자료 구조
Hash 검색을 위한 자료 구조를 만들기 위해서, 자료구조에 포함되어야 하는 값은 아래와 같이 나타낼 수 있다. 이해를 위해, 이전 포스팅에서 예시를 들었던 전화번호부의 필드명도 옆에 명시한다.
- 키 값(Key) -> 전화번호부에서 검색할 사람 이름
- 자료 값(Value) -> 전화번호부에서 실제 알고자 하는 사람의 전화번호
- 다음 값을 가리키는 특정 변수
이들 값이 배열의 특정 위치에 한 번에 저장이 되어야한다. 여러 변수를 하나의 형태로 저장하기 위해 Class를 사용하여 아래와 같이 새로운 자료형을 만들어준다(참고로 C언어에서는 구조체라는 것을 이용해 여러 변수를 하나의 형태로 저장한다).
* 새로 정의한 Class 내의 __init__ 함수 내에 정의된 인자를 보면, Class 이름인 Person_Info가 자료형으로 저장되어 있는데, 동일한 클래스를 자료형으로 메서드 인자로 활용하기 위해서 from __future__ import annotations를 가장 앞줄에 선언해주어야 한다.
이 자료형은 인접한 자료를 가리키기 위한 Pointer를 가져야 하고, 인접한 자료는 우리가 정의한 Person_Info와 동일한 자료형이기 때문에, __init__ 인자에 next_info라는 인자명으로 Person_Info 자료형이 추가되어야 함을 명시해주었다. 해당 인자가 포함되지 않을 때는 None 값이 저장되도록 정의했다.
이제 이 자료형이 배열에 저장될 수 있도록 아래와 같이 배열과 연관된 Class를 별도로 정의해보려 한다.
3. 연결 리스트를 고려한 Hash 검색 자료구조 코드
기본적으로 사용하는 Hash 검색 자료구조는 일반 Hash 검색 자료구조와 동일하다. 다만, 값을 저장하고, 삭제하는 과정에서 연결 리스트들이 참조하는 값들이 달라지기 때문에, 검색과 삭제를 관장하는 메서드들은 이전 포스팅에서 작성했던 내용과는 조금 다른 형태를 띄게 된다.
(1) 값의 저장(save_value)
값을 저장하기 위한 hash_list 클래스의 메서드는 위와 같이 작성한다. 충돌없이 hash 검색으로 값이 저장되도록 하는 코드는 사실 크게 어렵지 않다. 하나씩 살펴보자.
전화번호를 저장하기 위해서, 사람 이름(Key)과 전화번호(Value)를 인자로 받아야 한다. 따라서, save_value 메서드 사용 시, 이 두 인자를 받을 것임을 명시해둔다.
메서드의 인자 중 key 값은 Hash값 추출에 사용된다. 이전에 작성한 hash_function() 메서드를 이용해, 배열 내에 저장할 위치를 반환받는다.
저장할 위치에 값이 있는지 없는지 확인하는 조건이 바로 self.hash_list(index) == None 이다. 클래스를 선언하면서 None값만 들어가 있는 배열만 존재할 것인데, 아무 값도 등록되어 있는 상태가 아니라면 조건문 내에서 배열의 특정 위치에 값을 저장하는 코드를 작성하고 메서드를 종료하면 된다.
값을 저장할 때 주의할 점이 하나 있는데, 저장되는 값은 우리가 초반부에 선언한 Person_Info 객체 형태로 배열에 저장되어야 한다는 것이다. Person_Info 클래스 내에, 다음 Person_Info 값을 바라볼 수 있도록 변수가 선언되어 있기 때문에 Person_Info 객체 형태가 아닌 value값을 저장하게 되면 Hash 충돌 시, 다음 값을 참조할 수 없게 되기 때문이다.
먼저 빈 배열에 "김철수"에 대한 전화번호를 저장해보자. 그리고 "김철수"에 대한 정보가 저장된 배열 위치에서 다음 참조값을 호출해보자.
메인 실행 코드 결과를 보면, Hash_List 클래스 선언 시 생성되는 [None, None] 형태의 배열이 아닌, [Person_Info객체, None]이 나타나는 것을 볼 수 있다. Person_Info 객체가 저장된 위치에서 저장된 객체의 key, value, next_info 값을 확인하면 우리가 저장했던 값이 고스란히 나타나는 것을 볼 수 있다.
다음으로, "박희동"의 전화번호를 저장해보자. "박희동"과 "김철수"라는 키 값은, 필자가 정의한 배열과 Hash 값 추출 함수에 의하면 배열 내 동일한 위치에 값이 저장된다. 뒤에 저장되는 "박희동"의 정보는 배열의 특정 위치에서 참조하는 값이 되기 때문에 박희동의 정보가 저장되는 Person_Info 객체의 next_info 값은 "김철수"의 Person_Info 객체를 참조해야 한다.
즉, 저장 위치의 배열 값이 None이 아니라, 미리 저장된 Person_Info 객체가 존재하는 경우, 미리 저장된 객체를 새로 저장할 객체의 next_info 변수가 참조할 수 있도록 만들면 된다. 그림으로 나타내면 아래와 같은 절차로 진행된다.
save_info 메서드의 코드에 조금 변화를 가미하여, 실제 값이 저장되는 절차를 확인해보면 아래와 같이 나타난다.
(2) 저장값 Hash 검색(search_value)
Chaining으로 Hash 충돌을 고려하여 값을 저장하는 코드를 생성하는 것을 이해했다면, 값을 검색하는 메서드 코드를 작성하는 것은 조금 더 쉽게 진행할 수 있다. 인자로 받은 key 값으로 Hash 값을 추출하여 Index 값을 얻고, 배열의 해당 Index 내에 저장된 Person_Info 객체 중, key 값이 일치하는 Person_Info 객체의 value 값만 반환하면 되기 때문이다. key 값이 일치하지 않는 경우, Person_Info 객체의 next_info 값이 None이 될 때까지 루프를 사용하면 된다. 검색 메서드의 코드는 아래와 같다.
hash_list[index]를 별도의 변수가 참조하도록 만든 것을 볼 수 있는데, 변수 없이 직접 hash_list[index]가 검색값을 참조하도록 할 경우, 저장되어 있는 정보가 모두 깨져버리기 때문이다. present_info 대신 self_hash_list[index]로 해당 코드를 작성하고, 가장 처음에 저장된 "김철수"를 검색한 뒤 "박희동"을 검색하면 "박희동"의 검색값이 나타나지 않는다.
Python의 경우, 변수에 값이 저장되는 것이 아니라, 변수명이 변수값을 참조(Reference)하는 형태다. 따라서 hash_list[index]가 검색 메서드에 직접 참여하게 될 경우, 아래와 같은 절차로 검색이 진행되면서 연결 리스트가 깨지게 된다.
(3) 값의 삭제(remove_value)
값의 삭제는 저장 및 검색과 달리, 이전의 정보를 참조하는 변수가 추가로 필요하다. 배열의 특정 위치에 연결 리스트로 값이 쭉 저장되어 있고, 연결 리스트의 가운데에 위치한 저장 정보를 삭제하게 될 경우, 삭제되는 저장정보 앞의 next_info 변수가 삭제되는 저장정보 다음의 Person_Info 객체를 참조할 수 있도록 수정해주어야 하기 때문이다.
삭제와 관련된 메서드의 코드는 아래와 같이 작성하면 된다.
값의 삭제 메서드 역시, 직접적으로 배열이 값을 참조하게 하지 않고, 선언된 변수가 배열 내 정의된 연결 리스트를 참조하도록 작성하면 된다.
코드의 동작 과정에서 previous_info가 None인지의 여부에 따라, 실행 코드가 달라지는데, 이는 배열[index]에 연결 리스트로 값이 저장되어 있는 경우, 찾는 값이 가장 최근에 저장된 값인지에 여부에 따라 동작이 달라져야 하기 때문이다. 가장 최근에 저장된 값은 hash_list[index]에 의해 직접 값을 참조받으므로, 만약 이 값이 삭제되어야 한다면 hash_list[index]가 삭제되는 값 다음의 Person_Info객체를 직접적으로 참조하도록 만들어야 한다. 반면, 배열 리스트의 중간이나 마지막에 저장된 Person_Info가 삭제되어야 하는 경우, 삭제되어야 하는 Person_Info 이전의 Person_Info 객체에 정의된 next_info 변수가, 삭제되는 Person_Info 대신, 그 다음의 Person_Info 객체를 참조해야 한다.
위에서 만든 삭제 메서드를 이용하여, 이전에 생성한 연결 리스트 정보에서 값을 삭제한 결과는 아래와 같이 나타난다. 이영숙 -> 최영희 -> 박희동 -> 김철수 순으로 나열된 연결 리스트에서는 "최영희"와 "김철수"의 검색 결과가 반환되는 것을 확인할 수 있다. 그러나, 두 사람에 대한 정보를 remove_value로 삭제 후, 다시 검색을 진행하면, 검색값이 없다는 문구만 출력되는 것을 확인할 수 있다.
이번 포스팅에서는 Hash 충돌을 해결할 수 있는 알고리즘 중 하나인 Chaining에 대해 알아보았다. Chaining은 선언할 수 있는 배열의 크기가 작더라도, 배열 크기 이상의 값을 저장할 수 있기 때문에, 저장할 정보의 용량이 미리 정해지지 않은 경우 사용하기 적합하다. 그리고, 적당한 배열 크기가 선언되고, 적합한 Hash 코드 추출 함수가 존재하여 저장할 정보들이 배열 내에 골고루 저장될 수 있다면 값의 저장, 검색 및 삭제 복잡도도 O(1)로 매우 좋은 편이다.
반면, 배열의 크기가 너무 작아 저장해야 하는 정보들의 Hash 충돌이 증가하거나, 배열의 크기가 충분히 크더라도 부적합한 Hash 코드 추출 함수가 사용되어 대부분의 저장값이 하나의 Index에서 연결리스트를 형성하게 되는 경우, 선형 검색과 동일하게 검색, 저장, 삭제 모두 최대 O(n)의 복잡도를 가지게 되며 사용되지 않는 배열에 의해 메모리 낭비가 심해지게 된다. 따라서, Chaining을 사용하고자 한다면, 사용 전 예상되는 저장 정보의 용량을 통해 적절한 크기의 배열을 선언하는 것과, 이들 정보를 배열 내에 골고루 분산시킬 수 있는 Hash 코드 추출 방법을 고안하는 것이 매우 중요하다.
다음 포스팅에서는 Hash 충돌을 해결할 수 있는 두 번째 알고리즘인 개방 주소법(Open Addressing)에 대해 작성하려 한다.
Fin.
'Python > Python Data Structure and Algorithm' 카테고리의 다른 글
| [자료구조 with Python] 8. 정렬 알고리즘(1) - 버블 정렬 개요 (0) | 2024.03.07 |
|---|---|
| [자료구조 with Python] 7. 선형 자료 구조 - 배열(6), Hash 충돌과 개방 주소법(Open Address) (0) | 2024.03.05 |
| [자료구조 with Python] 5. 선형 자료 구조 - 배열(4), Hash검색 (0) | 2021.01.10 |
| [자료구조 with Python] 5. 선형 자료 구조 - 배열(3), 선형/이진 검색 (0) | 2021.01.05 |
| [자료구조 with Python] 4. 선형 자료 구조 - 배열(2), 기본 메서드/함수 동작 (0) | 2021.01.02 |
댓글