Hash Table

해시 테이블은 키(key)와 값(value)을 사용하는 데이터 구조이다. 해시테이블은 값을 빠르게 찾아야할때 사용하며 해시테이블에 값을 저장하는 방법은 다음과 같다.

1. 키값에 해시 함수를 사용하여 해시 값을 얻는다.
2. 해시 값을 나머지 연산자(modulo operator, %)를 이용하여 해쉬 테이블의 크기로 나누어 인덱스를 얻는다. (예를 들어 크기가 256인 해시 테이블의 해시 값을 256으로 나누면 0과 255사이의 나머지가 생긴다.)
3. 인덱스에 값을 저장하는데 이때 인덱스에 값이 이미 존재하는 충돌(Collision)이 일어난다면 연결리스트를 사용하여 같은 인덱스에 여러개의 값을 저장할 수 있다.

스위프트는 보안상의 이유로 프로그램을 실행할때마다 해시값이 변한다.

Time Complexity

해시 테이블의 동작들(검색, 삽입, 삭제 등)은 일반적으로 O(1)의 시간 복잡도를 가진다. 하지만 충돌이 많이 일어나는 경우에는 O(n)의 복잡도를 가질 수 있다.

Hash Table in Swift

// Linked List
class HashEntry {
    var key: String
    var value: String
    var next: HashEntry?
    
    init(_ key: String, _ value: String) {
        self.key = key
        self.value = value
    }
}

class HashTable {
    private static let initialSize = 256
    private var entries = Array<HashEntry?>(repeating: nil, count: initialSize)
    
    func put(_ key: String, _ value: String) {
        // Get the index
        let index = getIndex(key)
        
        // Create entry
        let entry = HashEntry(key, value)
        
        // If entry is not already there - store it
        if entries[index] == nil {
            entries[index] = entry
        }
        // else handle collision by appending to our linked list
        else {
            var collisions = entries[index]
            
            // Walk to the end
            while collisions?.next != nil {
                collisions = collisions?.next
            }
            
            // Add collision there
            collisions?.next = entry
        }
    }
    
    func get(_ key: String) -> String? {
        // Get the index
        let index = getIndex(key)
        
        // Get current list of entries for this index
        let possibleCollisions = entries[index]
        // Walk our linked list looking for a possible match on the key (that will be unique)
        var currentEntry = possibleCollisions
        while currentEntry != nil {
            if currentEntry?.key == key {
                return currentEntry?.value
            }
            currentEntry = currentEntry?.next
        }
        
        return nil
    }
    
    private func getIndex(_ key: String) -> Int {
        // Get the key's hash code
        let hashCode = abs(key.hashValue)
        
        // Normalize it into an acceptable index
        let index = hashCode % HashTable.initialSize
        print("\(key) \(hashCode) \(index)")
        
        return index
    }

    func prettyPrint() {
        for entry in entries {
            if entry == nil {
                continue
            }
            if entry?.next == nil {
                // nothing else there
                print("key: \(String(describing: entry?.key)) value: \(String(describing: entry?.value))")
            } else {
                // collisions
                var currentEntry = entry
                while currentEntry?.next != nil {
                    print("💥 key: \(String(describing: currentEntry?.key)) value: \(String(describing: currentEntry?.value))")
                    currentEntry = currentEntry?.next
                }
                print("💥 key: \(String(describing: currentEntry?.key)) value: \(String(describing: currentEntry?.value))")
            }
        }
    }
    
    // 스위프트의 딕셔너리 처럼 대괄호 안에 키 값을 저장하거나 읽기 위한 코드
    subscript(key: String) -> String? {
        get {
            get(key)
        }
        set(newValue) {
            guard let value = newValue else { return }
            put(key, value)
        }
    }
}