소개

소프트웨어 개발에서 가장 자주 사용하는 데이터 구조 중 하나인 해시표를 실현할 때다!
해시표는 관련 그룹을 실현하는 데이터 구조로 우리가 예상한 O(1) 시간 (O(n) - 오류가 발생한 최악의 경우) 에 접근할 수 있는 키와 값을 저장할 수 있도록 한다.
개인적으로 나는 이런 데이터 구조를 좋아한다.얘 약간 마술 같아!어떻게 정해진 시간에 랜덤 키의 값에 접근합니까?
다음은 작업 원리입니다.

해시 테이블에서 예상한 키/값 대수와 같은 길이의 그룹을 만듭니다.진열이 클수록 충돌 가능성은 낮다.

해시 함수를 만듭니다. 이 함수는 추가할 키의 값을 가져와 숫자로 변환합니다.이 함수가 좋을수록 충돌할 기회가 낮다.

산열 함수로 생성된 숫자를 추출하고 수조의 길이를 계산하는 모형.(예를 들어 해시가 1234이고 수조의 길이가 100이면 1234% 100으로 계산한다).이것은 그룹에 저장된 값의 인덱스가 될 것입니다.

요컨대 이것이 바로 그것의 작업 원리다.해시 맵에서 가장 중요한 일 중 하나는 아마도 해시 함수일 것이다.그것은 좋은 산열도와 매우 나쁜 산열도를 구분할 수 있다.
다음 구현에서는 문자열 키만 허용하는 해시 테이블에 대해 다음 해시 함수를 사용합니다.char[0] * 31^n-1 + char[1] * 31^n-2 + ... + char[n-1]그 밖에 나는 이미 여러 차례 상술한 충돌을 언급했다.두 개의 서로 다른 키의 그룹 인덱스가 서로 일치하면 충돌이 발생한다.이것은 아마도 해시 함수가 좋지 않거나 밑바닥 수조가 너무 작기 때문일 것이다.하지만 이 두 가지 문제는 모두 해결할 수 있다.더 좋은 해시 함수를 사용할 수 있고, 필요할 때 동적 성장 그룹을 사용할 수 있습니다.
하지만 충돌이 일어난다면 우리는 어떻게 해야 합니까?우리는 값을 미해시 키와 함께 체인 테이블 (또는 그룹) 에 저장할 것이지, 원래대로 그룹에 저장하지 않을 것이다.따라서 키 값을 검색하거나 수정하려고 할 때마다 체인 테이블을 훑어보고 정확한 키를 조작하고 있는지 확인합니다.
다행히도 우리는 이미 체인 시계를 실현했다.여기서 사용합니다:)

Go의 데이터 구조: 체인 테이블

다림・ 2019년 12월 22일・ 4분 읽기

#go #linkedlist #linked #list

다음은 해시 시계의 그림입니다.

(출처: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Hashing/hashing.html

실시

우선, 우리는 밑바닥 데이터 저장을 위해 그룹 크기를 선택할 것이다.현재 구현에서, 이것은 변하지 않지만, 더 높은 버전은 키 수가 그룹 길이에 도달할 때 동적으로 더 큰 그룹을 만들 수 있습니다.

const arrayLength = 100

그리고 평소와 같이 우리는 데이터 구조를 위한 구조를 만든다.우리가 유일하게 가지고 있는 필드는 그룹입니다. 모든 요소는 체인 테이블을 가리키는 바늘 (github.com/dorin131/go-data-structures/linkedlist) 입니다.

type HashTable struct {
    data [arrayLength]*linkedlist.LinkedList
}

다음은 체인 테이블 노드의 내용을 위한 또 다른 구조 유형을 만듭니다.이 구현에서, 키는 문자열이어야 하며, 값은 모든 종류가 될 수 있습니다.

type listData struct {
    key   string
    value interface{}
}

우리는 구조 함수도 하나 추가했다.

func New() *HashTable {
    return &HashTable{
        [arrayLength]*linkedlist.LinkedList{},
    }
}

앞에서 논의한 바와 같이, 우리는 산열 키의 인덱스를 얻기 위해 산열 함수와 함수가 필요하다.

func hash(s string) int {
    h := 0
    for pos, char := range s {
        h += int(char) * int(math.Pow(31, float64(len(s)-pos+1)))
    }
    return h
}

func index(hash int) int {
    return hash % arrayLength
}

Set과Get방법을 추가할 때입니다.우리는 지도에 키를 추가한 후에 키의 값을 각각 검색할 수 있다.Set 방법에서 우리는 먼저 키의 색인을 계산하고 먼저 그것을 산열한 다음에 모형을 얻는다.그리고 만약 이 위치에 아무런 내용이 없다면, 우리는 새로운 체인 테이블을 초기화합니다. 그렇지 않으면 목록을 훑어보고 기존 값을 업데이트하거나 새 값을 추가해야 하는지 확인합니다.

func (h *HashTable) Set(k string, v interface{}) *HashTable {
    index := index(hash(k))

    if h.data[index] == nil {
        h.data[index] = linkedlist.New()
        h.data[index].Append(listData{k, v})
    } else {
        node := h.data[index].Head
        for {
            if node != nil {
                d := node.Data.(listData)
                if d.key == k {
                    d.value = v
                    break
                }
            } else {
                h.data[index].Append(listData{k, v})
                break
            }
            node = node.Next
        }
    }
    return h
}

Get 방법에 대해 우리는 같은 것부터 색인을 계산한 다음에 체인 테이블을 보고 값을 찾습니다.

func (h *HashTable) Get(k string) (result interface{}, ok bool) {
    index := index(hash(k))
    linkedList := h.data[index]

    if linkedList == nil {
        return "", false
    }
    node := linkedList.Head
    for {
        if node != nil {
            d := node.Data.(listData)
            if d.key == k {
                return d.value, true
            }
        } else {
            return "", false
        }
        node = node.Next
    }
}

결론

현재 구현된 다음 단계는 베이스 어레이를 확장할 수 있도록 하는 것이다.내가 남겨줄게.어떻게 했는지 알려줘!

테스트 소스 코드

dorin131 / go 데이터 구조

Go에서 구현된 데이터 구조 집합

비디오