해시 테이블 (산 목록) - swift 구현

정의.

해시 표 는 키워드 key 를 통 해 검색 과 저장 을 실현 하 는 구조 로 해시 방법 을 통 해 저장 값 의 위치 와 key 사이 에 확정 적 이 고 대응 하 는 관 계 를 구축 하여 모든 key 가 하나의 저장 위치 에 대응 하도록 한다.

해시 방법 은 해시 함수 나 해시 함수 라 고도 부른다.

대부분의 언어 에서 사전 은 산 목록 을 통 해 이 루어 진 것 이 고 Swift 에서 도 열 리 지 않 으 며 Swift 에서 사전 의 key 는 Hashable 협 의 를 지 켜 야 한다.

특성 설명

사실은 산 목록 은 하나의 배열 이지 만 구체 적 으로 value 를 저장 하 는 위 치 는 key 를 특정한 '알고리즘' 에 가 져 와 계산 한 것 이다.

위의 특정한 알고리즘 은 여러 가지 가 있 는데 예 를 들 어 직접 주소 법, 제곱 취 중 법, 잉여 법, 랜 덤 수법 등 이다.그러나 모든 방법 은 불가피 하 다. 키 1, 키 2 두 개의 서로 다른 값 이 존재 하지만 알고리즘 을 통 해 계산 한 후에 얻 은 배열 에서 같은 저장 위 치 는 이때 충돌 이 생 긴 다.

충돌 을 피 하 는 것 도 알고리즘 과 마찬가지 로 여러 가지 가 있 습 니 다. 예 를 들 어 재 산열 법, 체인 주소 법 등 아래 에서 받 아들 이 는 실현 은 바로 체인 주소 법 을 통 해 이 루어 진 것 입 니 다.

한 마디 로 산 목록 을 실현 하 는 취 지 는 계산 (즉 알고리즘) 이 상대 적 으로 간단 해 야 하 는 동시에 배열 의 위치 분 포 는 상대 적 으로 고 르 고 물고기 와 곰 발바닥 을 가능 한 한 겸 해 야 한 다 는 것 이다.

이루어지다
사전 으로 는 key 에 따라 읽 기, 업데이트, 저장 값 을 읽 을 수 있 으 며, 이러한 특성 에 따라 이 루어 집 니 다.

//0
struct HashTable {
    //1
    private typealias Element = (key: Key, value: Value)
    private typealias Bukets = [Element]
    //2
    private var buckets: [Bukets]
    private(set) var count = 0
    
    var isEmpty: Bool { return count == 0 }
    //3
    init(_ capacity: Int) {
        assert(capacity > 0, "     ")
        buckets = Array.init(repeating: [], count: capacity)
    }
  //4
    private func index(forKey key: Key) -> Int {
        return abs(key.hashValue) % buckets.count
    }
}

0. 두 개의 범 키 와 Value 좌석 키 - 값 의 유형 을 정의 합 니 다. 그 중에서 Key 는 HashTable 을 계승 해 야 합 니 다.
1. 두 가지 유형, 하나의 원조, 원 조 를 포함 하 는 배열 형식 을 정의 합 니 다.
2. 산 목록 메모리 에 데 이 터 를 저장 하 는 배열 을 정의 합 니 다. 이 buckets 의 유형 은 [Bukets] 이 고 내부 요 소 는 배열 입 니 다. 배열 의 요 소 는 원 그룹 입 니 다. [(key: Key, value: Value), (key: Key, value: Value)], [(key: Key, value: Value), (key: Key, value: Value)], [(key: Key, value: Value)]]
3. 내부 용량 을 초기 화 방법 으로 설정

index 방법 을 통 해 key 가 대응 하 는 value 의 아래 표 시 된 값 을 계산 합 니 다. 여기 서 사용 하 는 방법 은 나머지 를 제외 한 방법

입 니 다.
아래 표 시 를 통 해 이전, 삭제, 검사 의 조작 을 실현 하 다.

private func value(forKey key: Key) -> Value? {
        let index = self.index(forKey: key)
        for element in buckets[index] {
            if element.key == key {
                return element.value
            }
        }
        return nil
    }
    
    private mutating func upDateValue(value: Value, forKey key: Key) {
        let index = self.index(forKey: key)
        for (i, element) in buckets[index].enumerated() {
            if element.key == key {
                let bucketElement = buckets[index]
                var keyValue = bucketElement[i]
                keyValue.value = value
                return
            }
        }
        //      key，     
        buckets[index].append((key, value))
        count += 1
    }
    
    private mutating func removeValue(forKey key: Key) -> Value? {
        let index = self.index(forKey: key)
        for (i, element) in buckets[index].enumerated() {
            if element.key == key {
                 buckets[index].remove(at: i)
                count -= 1
                return element.value
            }
        }
        return nil
    }
    
    ///            
    subscript(key: Key) -> Value? {
        get {
            return value(forKey: key)
        }
        set {
            if let value = newValue {
                upDateValue(value: value, forKey: key)
            } else {
                let _ = removeValue(forKey: key)
            }
        }
    }

이상 은 산 목록 에 대한 간단 한 실현 이 고 그 후에 점차적으로 완 선 될 것 이다.