golang hashmap 실현, 자동 신축

golang hashmap 데이터 구조 구현
간단 한 소개
해시 표 는 키 쌍 을 저장 하 는 데이터 구조 로 해시 표 에서 삭제 하고 삽입 작업 을 하면 O (1) 의 시간 효율 에 거의 도달 할 수 있다.쉽게 말 하면 하 쉬 시 계 는 배열 과 링크 의 결합 이다. 하 쉬 시 계 를 잘 이해 하기 위해 먼저 내 가 hashmap 을 테스트 할 때의 출력 을 보고 하 쉬 표 의 구 조 를 이미지 적 으로 묘사 했다.
0:—–>&{20 atongmu } 1:—–>&{61 atongmu } 2: 3: 4: 5: 6: 7:—–>&{67 atongmu } 8:—–>&{68 atongmu } 9: 10: 11: 12: 13: 14: 15:—–>&{35 atongmu } 16:—–>&{16 atongmu 0xc0420024e0}—–>&{76 atongmu } 17:—–>&{57 atongmu } 18:—–>&{58 atongmu } 19:—–>&{79 atongmu }
이 덩어리 는 바로 해시 표 로 시계 머리 와 데이터 체인 으로 구성 되 어 있다.맨 왼쪽 에 있 는 열 은 헤더 입 니 다. 이 열 은 배열 로 구 성 된 것 입 니 다. 모든 헤더 에 데 이 터 를 저장 하지 않 고 데이터 체인 의 지침 만 있 습 니 다. entry 가 이 위치 에 저장 되 지 않 으 면 지침 은 nil 입 니 다.배열 의 아래 표 시 는 표 머리 가 bucket 의 이마 에 있 는 위 치 를 나타 내 고 모든 key 의 hash 값 입 니 다.오른쪽 에 있 는 모든 것 이 데이터 체인 입 니 다. 해시 표 가 공간 에서 가 벼 운 양 을 차지 하 는 동시에 O (1) 의 검색, 삽입, 삭제 시간 효율 을 달성 하기 위해 부하 인 자 를 통 해 bucket 의 길 이 를 자동 으로 조절 해 야 합 니 다.
주요 특징

나의 hashmap 가 사용 하 는 key 수신 int, value 수신 string

부하 인자 (이미 entry 수 / bucket 용량) 가 0.75 보다 크 면 자동 확장

put 시 hashmap 에 이 키 가 있 는 것 을 발견 하면 value

를 직접 덮어 씁 니 다.

put 시 키 의 hash 값 이 표 에 결점 이 있 는 것 을 발견 하면 이 결점 이 있 는 링크 끝 에 추가 합 니 다

관건 유형, 상수, 변수 및 함수 소개
1. Entry 와 HashMap 유형

type Entry struct {
    key   int
    value string
    next  *Entry
}  

Entry 는 키 쌍 과 다음 Entry 지침 을 저장 합 니 다. hashmap 의 모든 노드 를 설명 합 니 다.

type HashMap struct {
    size    int
    buckets []Entry
}

HashMap 유형 은 전체 hashmap 입 니 다. 크기 를 설명 하고 Entry 형식의 절편 으로 이 루어 집 니 다.
2. 전역 상수, 변수

const maxCapacity int = 100    
const loadFactor float32 = 0.75     
var nowCapacity int = 10   

maxCapacity hashmap 에서 bucket 의 최대 확장 용량 을 정의 합 니 다. 즉, hashmap 는 자동 으로 크기 를 늘 려 사용 효율 을 높 일 수 있 지만 끊임없이 확장 할 수 없습니다. loadFactor 부하 인 자 를 정의 합 니 다. 표 에서 entry 수량 이 현재 용량 의 부하 인자 에 이 르 렀 을 때 (이 곳 은 0.75) 용량 이 배로 nowCapacity변수 로 현재 표 의 부하 능력 을 저장 합 니 다. 즉, bucket 의 길이 입 니 다.
3. CreateHashMap () 새 hashmap

func CreateHashMap() *HashMap {
    hm := &HashMap{}
    hm.size = 0
    hm.buckets = make([]Entry, nowCapacity, maxCapacity)
    return hm
}

사용 자 는 이 함 수 를 호출 하여 hashmap 를 만 들 고 초기 화 할 수 있 습 니 다. hashmap 의 size (초기 Entry 개수), 초기 부하 및 최대 부하 가 초기 화 되 었 습 니 다.
4. getHash () 키 의 해시 값 가 져 오기

func getHash(k int) int {
    return k % nowCapacity
}

내 가 정의 한 key 는 int 형식 이기 때문에 간단 한 나머지 제거 법 으로 key 의 해시 값 을 가 져 옵 니 다.
5. DeleteEntry (k int) 는 hashmap 에서 key 에 대응 하 는 Entry 를 삭제 합 니 다.

//    key Entry
func (hm *HashMap) Delete(k int) bool {
    e, ok := hm.GetEntry(k)
    if ok {
        fmt.Println("  Entry, hash ：", getHash(e.key), "  ：", e)
        hm.DeleteEntry(e)
        return true
    } else {
        fmt.Println("   Entry，    ")
        return false
    }
}

봉 인 된 GetEntry (key int) 와 DeleteEntry (e * Entry) 를 호출 하여 이 key 가 있 는 Entry 를 먼저 찾 아 삭 제 를 실행 합 니 다.
6. Put (k int, v value) 는 hashmap 에 데 이 터 를 삽입 하고 부하 정 도 를 측정 하여 자동 으로 용량 을 조절 합 니 다.

func (hm *HashMap) Put(k int, v string) {

    e := &Entry{k, v, nil}
    hm.insert(e)
    //            ，       
    if float32(hm.size)/float32(nowCapacity) >= loadFactor && nowCapacity < maxCapacity {
        if 2*nowCapacity > maxCapacity {
            nowCapacity = maxCapacity
        } else {
            nowCapacity = 2 * nowCapacity
        }
        newHm := CreateHashMap()

        var index int
        for index = 0; index < len(hm.buckets); index++ {
            p := hm.buckets[index].next
            for p != nil {
                //    p next
                pNext := p.next
                p.next = nil
                newHm.insert(p)
                p = pNext
            }
        }

        var b1 int
        var b2 int = len(newHm.buckets)

        // hm      newHm   
        for b1 = len(hm.buckets); b1 < b2; b1++ {
            hm.buckets = append(hm.buckets, Entry{})
        }
        //     
        for b1 = 0; b1 < b2; b1++ {
            hm.buckets[b1].next = newHm.buckets[b1].next
            newHm.buckets[b1].next = nil
        }
    }
}

먼저 호출 insert 함수 가 직접 키 값 을 hashmap 에 삽입 한 다음 에 확장 이 필요 한 지 확인 합 니 다. float32(hm.size)/float32(nowCapacity) >= loadFactor 부하 인 자 를 초과 했다 고 표시 합 니 다. nowCapacity < maxCapacity 확장 공간 이 있다 고 표시 합 니 다. 이 두 가지 조건 을 만족 시 킬 때 새 용량 이 배로 (또는 직접 값 max Capacity) 의 새로운 hashmap 을 만 들 고 데 이 터 를 이전 합 니 다.
전체 코드 구현

package hashmap

import (
    "fmt"
)

const maxCapacity int = 100     //bucket     
const loadFactor float32 = 0.75 //    

var nowCapacity int = 10 //    

type Entry struct {
    key   int
    value string
    next  *Entry
}

type HashMap struct {
    size    int
    buckets []Entry
}

func CreateHashMap() *HashMap {
    hm := &HashMap{}
    hm.size = 0
    hm.buckets = make([]Entry, nowCapacity, maxCapacity)
    return hm
}

//  key hash
func getHash(k int) int {
    return k % nowCapacity
}

func (hm *HashMap) GetSize() int {
    return hm.size
}

// key hashMap    Entry  
func (hm *HashMap) GetEntry(k int) (*Entry, bool) {
    p := hm.buckets[getHash(k)].next
    for p != nil {
        //  ,  
        if p.key == k {
            return p, true
        } else {
            p = p.next
        }
    }
    //  p==nil，   
    return nil, false
}

//           ,   hashmap  entry
func (hm *HashMap) insert(e *Entry) {

    hash := getHash(e.key)
    //           
    var p *Entry = &hm.buckets[hash]
    for p.next != nil {
        //       key，       ,  insert，return
        if p.next.key == e.key {
            p.next.value = e.value
            return
        } else {
            p = p.next
        }
    }
    //  p      
    p.next = e
    hm.size++
}

//           insert
func (hm *HashMap) Put(k int, v string) {
    e := &Entry{k, v, nil}
    hm.insert(e)
    //            ，       
    if float32(hm.size)/float32(nowCapacity) >= loadFactor && nowCapacity < maxCapacity {
        if 2*nowCapacity > maxCapacity {
            nowCapacity = maxCapacity
        } else {
            nowCapacity = 2 * nowCapacity
        }

        newHm := CreateHashMap()
        var index int
        for index = 0; index < len(hm.buckets); index++ {
            p := hm.buckets[index].next
            for p != nil {
                //    p next
                pNext := p.next
                p.next = nil
                newHm.insert(p)
                p = pNext
            }
        }

        var b1 int
        var b2 int = len(newHm.buckets)

        // hm      newHm   
        for b1 = len(hm.buckets); b1 < b2; b1++ {
            hm.buckets = append(hm.buckets, Entry{})
        }
        //    
        for b1 = 0; b1 < b2; b1++ {
            hm.buckets[b1].next = newHm.buckets[b1].next
            newHm.buckets[b1].next = nil
        }
    }
}

//    Entry
func (hm *HashMap) DeleteEntry(e *Entry) {
    //       p:=hm.buckets[getHash(e.key)].next,            nil
    p := &hm.buckets[getHash(e.key)]
    for p != nil {
        if p.next == e {
            fmt.Println("    ")
            p.next = p.next.next
            fmt.Println("    ")

            hm.size--
            return
        } else {
            p = p.next
        }
    }
    fmt.Println("    ")
}

//    key Entry
func (hm *HashMap) Delete(k int) bool {
    e, ok := hm.GetEntry(k)
    if ok {
        fmt.Println("  Entry, hash ：", getHash(e.key), "  ：", e)
        hm.DeleteEntry(e)
        return true
    } else {
        fmt.Println("   Entry，    ")
        return false
    }
}

//  hashMap
func (hm *HashMap) Traverse() {
    var index int
    for index = 0; index < nowCapacity; index++ {
        p := hm.buckets[index].next
        if p == nil {
            fmt.Println(index, ":")
        } else {
            fmt.Print(index, ":")
        }
        for p != nil {
            fmt.Print("----->", p)
            p = p.next
            if p == nil {
                fmt.Println()
            }
        }
    }
    fmt.Println()
}