데이터 구조 와 알고리즘 (Golang 구현) (16) 흔 한 데이터 구조 - 사전
우 리 는 책 을 뒤 적 일 때 목록 을 찾 은 다음 에 우리 가 원 하 는 페이지 수 를 찾 아야 한다. 예 를 들 어 우리 가 어떤 영어 단 어 를 찾 을 때 영어 사전 에서 단어 표 목록 을 본 다음 에 단어의 페이지 를 찾 아야 한다.
컴퓨터 에 도 이런 수요 가 있다.
사전
사전 은 키 가 맞 는 데이터 구 조 를 저장 하 는 것 으로 하나의 키 와 하나의 값 을 매 핑 하여 일일이 매 핑 하고 키 는 중복 할 수 없습니다.일부 튜 토리 얼 에서 이런 구 조 는 기호 표, 관련 배열 또는 맵 이 라 고 할 수 있다.우 리 는 잠시 그것 을 사전 이 라 고 부 르 면 이해 하기 쉽다.
예:
=>
"cat"=>2
"dog"=>1
"hen"=>3
우리 가 키
cat 의 값 을 꺼 내 면 바로 2 이다.Golang 이 데이터 구 조 를 제공 했다. map 키 의 데이터 형식 은 비교 할 수 있어 야 한다. 비교 할 수 없 으 면 키 가 존재 하 는 지 없 는 지 알 수 없 기 때문이다.Golang 사전 의 일반적인 조작 은 다음 과 같다.
package main
import "fmt"
func main() {
// 4 map
m := make(map[string]int64, 4)
//
m["dog"] = 1
m["cat"] = 2
m["hen"] = 3
fmt.Println(m)
// hen
which := "hen"
v, ok := m[which]
if ok {
//
fmt.Println("find:", which, "value:", v)
} else {
//
fmt.Println("not find:", which)
}
// ccc
which = "ccc"
v, ok = m[which]
if ok {
//
fmt.Println("find:", which, "value:", v)
} else {
//
fmt.Println("not find:", which)
}
}
사전 의 실현 은 두 가지 방식 이 있다. 하 쉬 표
HashTable 와 검 은 나무 RBTree.Golang 언어 에서 사전 map 의 실현 은 해시 표 에 의 해 이 루어 지고 구체 적 으로 표준 라 이브 러 리 runtime 의 map.go 파일 을 참고 할 수 있다.우 리 는 장 에서 해시 검색 과 빨 간 검 은 나무 에서 사전 의 두 가지 실현 방식 을 구체 적 으로 분석 할 것 이다.
2. 중복 집합 불가 설정 실현
일반적으로 많은 프로 그래 밍 언어 라 이브 러 리 는 중복 집합
Collection 을 Set 이 라 고 명명 합 니 다. 이 Set 중국 어 를 집합 으로 직역 합 니 다. 어떤 문맥 에서 우리 의 뇌 는 자동 으로 걸 러 야 합 니 다. 집합 이라는 단 어 는 중복 집합 이 불가능 한 것 을 말 합 니까? 아니면 통칭 하 는 집합 을 말 합 니까? 여기 서 중국어 의 넓 고 심오 함 을 볼 수 있 습 니 다.중복 집합
Set 으로 데 이 터 를 저장 할 수 없 으 며 데이터 가 중복 되 지 않 고 무 거 워 지 는 것 이 특징 이다.데 이 터 를 넣 고 데 이 터 를 하나 더 넣 으 세 요. 두 데이터 가 같 으 면 한 개의 데이터 만 저장 합 니 다.집합
Set 은 순서 관계 가 없 을 수도 있 고 값 에 따라 정렬 하여 특수 한 목록 을 계산 할 수도 있다.사전 의 키 가 중복 되 지 않 는 다 는 것 을 알 기 때문에 사전 의 값 을 고려 하지 않 으 면 집합 을 실현 할 수 있 습 니 다. 우 리 는 정수 집합
Set 을 실현 합 니 다.//
type Set struct {
m map[int]struct{} // ，
len int //
sync.RWMutex // ，
}
2.1. 집합 초기 화
//
func NewSet(cap int64) *Set {
temp := make(map[int]struct{}, cap)
return &Set{
m: temp,
}
}
하나의 용량
cap 의 map 을 사용 하여 중복 집합 을 실현 할 수 없다.map 의 값 을 사용 하지 않 기 때문에 값 은 빈 구조 체 struct{} 로 정의 합 니 다. 빈 구조 체 가 메모리 공간 을 차지 하지 않 기 때 문 입 니 다.예:package main
import (
"fmt"
"sync"
)
func main()
//
a := struct{}{}
b := struct{}{}
if a == b {
fmt.Printf("right:%p
", &a)
}
fmt.Println(unsafe.Sizeof(a))
}
출력:
right:0x1198a98
0
빈 구조 체 의 메모리 주 소 는 모두 같 으 며 메모리 공간 을 차지 하지 않 습 니 다.
2.2. 요소 추가
//
func (s *Set) Add(item int) {
s.Lock()
defer s.Unlock()
s.m[item] = struct{}{} //
s.len = len(s.m) //
}
먼저, 동시 다발 자 물 쇠 를 추가 하여 스 레 드 안전 을 실현 한 다음 에 구조 체
s *Set 에 내 장 된 map 에 이 요 소 를 추가 합 니 다. item 요 소 는 사전 의 키 로 서 자동 으로 무 거 워 집 니 다.동시에 집합 크기 가 다시 생 성 된다.시간 복잡 도 는 사전 설정 키 값 의 복잡 도 와 같 습 니 다. 해시 가 충돌 하지 않 는 시간 복잡 도 는:
O(1) 입 니 다. 그렇지 않 으 면 O(n) 입 니 다. 해시 표 에서 한 장 을 실현 할 수 있 습 니 다.2.3. 요소 삭제
//
func (s *Set) Remove(item int) {
s.Lock()
s.Unlock()
//
if s.len == 0 {
return
}
delete(s.m, item) //
s.len = len(s.m) //
}
같은 이치 로 먼저 병발 자 물 쇠 를 추가 한 다음 에 삭제
map 안의 키: item.시간 복잡 도 는 사전 에서 키 값 의 복잡 도 를 삭제 하 는 것 과 같 습 니 다. 하 쉬 가 충돌 하지 않 는 시간 복잡 도 는: O(1) 입 니 다. 그렇지 않 으 면 O(n) 입 니 다. 하 쉬 표를 보면 한 장 을 실현 할 수 있 습 니 다.2.3. 원소 가 집합 중인 지 확인
//
func (s *Set) Has(item int) bool {
s.RLock()
defer s.RUnlock()
_, ok := s.m[item]
return ok
}
시간 복잡 도 는 사전 이 키 값 의 복잡 도 를 가 져 오 는 것 과 같 습 니 다. 하 쉬 가 충돌 하지 않 는 시간 복잡 도 는:
O(1) 입 니 다. 그렇지 않 으 면 O(n) 입 니 다. 하 쉬 표를 보면 한 장 을 실현 할 수 있 습 니 다.2.4. 집합 크기 보기
//
func (s *Set) Len() int {
return s.len
}
시간 복잡 도:
O(1).2.5. 집합 이 비어 있 는 지 확인
//
func (s *Set) IsEmpty() bool {
if s.Len() == 0 {
return true
}
return false
}
시간 복잡 도:
O(1).2.6. 모든 요소 집합 제거
//
func (s *Set) Clear() {
s.Lock()
defer s.Unlock()
s.m = map[int]struct{}{} //
s.len = 0 //
}
원래 의
map 를 풀 어 주 고 빈 map 을 다시 부여 합 니 다.시간 복잡 도:
O(1).2.7. 집합 을 목록 으로 전환
func (s *Set) List() []int {
s.RLock()
defer s.RUnlock()
list := make([]int, 0, s.len)
for item := range s.m {
list = append(list, item)
}
return list
}
시간 복잡 도:
O(n).2.8. 완전한 예
package main
import (
"fmt"
"sync"
"unsafe"
)
//
type Set struct {
m map[int]struct{} // ，
len int //
sync.RWMutex // ，
}
//
func NewSet(cap int64) *Set {
temp := make(map[int]struct{}, cap)
return &Set{
m: temp,
}
}
//
func (s *Set) Add(item int) {
s.Lock()
defer s.Unlock()
s.m[item] = struct{}{} //
s.len = len(s.m) //
}
//
func (s *Set) Remove(item int) {
s.Lock()
s.Unlock()
//
if s.len == 0 {
return
}
delete(s.m, item) //
s.len = len(s.m) //
}
//
func (s *Set) Has(item int) bool {
s.RLock()
defer s.RUnlock()
_, ok := s.m[item]
return ok
}
//
func (s *Set) Len() int {
return s.len
}
//
func (s *Set) Clear() {
s.Lock()
defer s.Unlock()
s.m = map[int]struct{}{} //
s.len = 0 //
}
//
func (s *Set) IsEmpty() bool {
if s.Len() == 0 {
return true
}
return false
}
//
func (s *Set) List() []int {
s.RLock()
defer s.RUnlock()
list := make([]int, 0, s.len)
for item := range s.m {
list = append(list, item)
}
return list
}
//
func other() {
a := struct{}{}
b := struct{}{}
if a == b {
fmt.Printf("right:%p
", &a)
}
fmt.Println(unsafe.Sizeof(a))
}
func main() {
//other()
// 5
s := NewSet(5)
s.Add(1)
s.Add(1)
s.Add(2)
fmt.Println("list of all items", s.List())
s.Clear()
if s.IsEmpty() {
fmt.Println("empty")
}
s.Add(1)
s.Add(2)
s.Add(3)
if s.Has(2) {
fmt.Println("2 does exist")
}
s.Remove(2)
s.Remove(3)
fmt.Println("list of all items", s.List())
}
출력:
list of all items [1 2]
empty
2 does exist
list of all items [1]
시리즈 문장 입구
저 는 진성 입 니 다. 제 가 직접 쓴 데이터 구조 와 알고리즘 (Golang 실현) 을 읽 는 것 을 환영 합 니 다. 글 은 더욱 우호 적 인 GitBook 을 읽 는 데 첫 발 을 내 디 뎠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
