[자료구조] 해시 충돌 해결

2021.08.01 - [자료구조] - [자료구조] Hash / Hash Function / Hash Table 에 이어서.

 

해시 함수가 서로 다른 key를 해시 값으로 변환했음에도 동일한 결과물이 나온 상황이다.

어떤 상황인지 코드와 함께 알아보자.

 

앞선 포스팅에서 10개의 데이터를 저장할 10개의 Slot을 지닌 해시테이블을 만들었다.

 

let keys = [10, 21, 32, 43, 54, 65, 76, 87, 98, 109] 
let values = ["홍길동", "이석훈", "강호동", "유재석", "박명수", "이효리", "하창수", "박지원", "김구", "윤봉길"]

func getHash(_ key: Int) -> Int { 
    let hashValue = key % hashTable.count // count == 10
    return hashValue 
}

 

이때 만약 10개가 아닌 11개의 데이터가 해시테이블에 저장되어야 한다면

준비 된 10개의 Slot중 한 곳에는 두개의 데이터가 들어가야만 하는 경우가 발생하게 된다.

 

keys는 총 10개의 값을 갖고 있었고 해시함수는 keys의 값들을 해시값으로 변환했을때 서로 중복되는 값이 존재하지 않았다.

 

keys[0] 부터 keys[9]까지 순차적으로 해시함수를 거쳤을 때

이미 해시테이블의 Slot은 모두 꽉 찬 상태가 된다.

 

우리는 여기서 120이라는 key를 갖고 있고 "BTS"라는 value를 가진 NameData 더 추가해야한다고 가정하자.

 

120을 해시함수를 통해 해시값으로 변환한 결과는 0이 되므로

keys[0]의 값인 10을 해시값으로 변환한 결과와 같다.

 

hashtable[0]의 자리엔 “홍길동”이 이미 저장되었는데, "BTS"가 새로이 저장되며 “홍길동”이 지워지게 되는 것이다.

 

 

 

충돌 해결

 

해시충돌을 처리하는 방식중 가장 많이 쓰이는것이

체이닝과 개방번지화다.

 

• 체이닝(Chaning, 각각의 해시 테이블의 인덱스에 해당 하는 자료구조를 연결리스트로 만드는 방법)
• 개방 번지화(Open Addressing, 해시테이블 인덱스 중 비어있는 공간을 할당하는 방법)

 

체이닝

 

해시 테이블의 Slot을 연결리스트로 구성함으로서 충돌을 방지하는 방법이다.

연결리스트는 이전 포스팅에서 이미 다뤄봤으니 설명은 생략한다. 충돌 방지에 대한 공부를 하고 있으니, 삽입 삭제등의 불필요한 코드는 삭제했다.

struct NameData { 
    let key: Int 
    let value: String 
}

class Node { 
    var prevAddress: Node? 
    var data: NameData? 
    var nextAddress: Node? 
    
    init(_ data: NameData) {
        self.data = data 
    }
    
    func printData() {
        print(data ?? "data is nil") 
    }
}

class LinkedList { 
    var head: Node? 
    var tail: Node? 
    
    func append(_ data: NameData) { 
        let newNode = Node(data) 
        if head == nil { 
            head = newNode 
            tail = newNode //추가 
        } else {
            newNode.prevAddress = tail
            tail?.nextAddress = newNode
            tail = newNode 
        }
    }
    
    func printDatas() { 
        var currnet = head
        while currnet != nil { 
            currnet?.printData() 
            currnet = currnet?.nextAddres
        }
    }
}

class HashTable { 
    var table: [LinkedList?] = .init(repeating: nil, count: 10) 
    
    private func getHash(_ key: Int) -> Int {
        let hashValue = key % table.count // count == 10 
        return hashValue 
    }
    
    func setData(_ data: NameData) { 
        let hashValue = getHash(data.key) 
        if table[hashValue] == nil {
            table[hashValue] = LinkedList() 
        }
        
        table[hashValue]!.append(data)
    }
    
    func printAll() {
        for (hashIndex, list ) in table.enumerated() { 
            print("\nhashIndex: \(hashIndex)")
            
            if list == nil { 
                print("isEmpty") 
                continue
            }
            
            list?.printDatas() 
            }
        }
    }

 

해시테이블의 저장타입이 이름정보만 있던 String에서 LinkedList로 바뀌었다. 또, Node의 data는 NameData로, LinkedList에 append할 때 키와 이름정보가 함께 들어간다.

 

키가 함께 저장되는 이유는 해시테이블의 각 요소가 리스트로 구성되기 때문에 검색 또는 삭제와 같은 수행을 할 때

연결리스트의 NameData의 key값을 검색 하고 삭제할 수 있게 하기 위해서다.