Golang (Go언어) 자료 구조(Data Structure) 2/2

Tucker의 Go 언어 프로그래밍 책과 유튜브를 통해 학습 중입니다.

Golang 마스 코트 Gopher(고퍼)

맵(Map)

- 키와 값 형태로 데이터를 저장하는 자료구조

- 언어에따라 딕셔너리(Dictionary), 해시 테이블(Hash table), 해시 맵(Hash map)등으로 부름. 

- 맵은 키와 값의 쌍으로 데이터를 저장하고, 키를 사용해 접근하여 값을 저장하거나 변경할 수 있음.

- 맵은 Go언어에서 패키지가 아닌, 기본 내장 타입이라 다른 패키지를 가져오지 않아도 사용할 수 있음.

map[key]value

 

→ map[] 안에 사용한 string은 키 타입이고, 맨 뒤에 있는 string은 값 타입임.

package main

import "fmt"

func main() {
	m := make(map[string]string)		// 맵 생성
	m["이화랑"] = "서울시 광진구"		// 키와 값 추가
	m["송하나"] = "서울시 강남구"
	m["백두산"] = "부산시 사하구"
	m["최번개"] = "전주시 덕진구"

	m["최번개"] = "청주시 상당구" 		// 값 변경

	fmt.Printf("송하나의 주소는 %s입니다.\n", m["송하나"])
	fmt.Printf("백두산의 주소는 %s입니다.\n", m["백두산"])
    fmt.Printf("최번개의 주소는 %s입니다.\n", m["최번개"])   // 값 변경 확인해보기
}

// 결과

송하나의 주소는 서울시 강남구입니다.
백두산의 주소는 부산시 사하구입니다.
최번개의 주소는 청주시 상당구입니다.  	// 청주시 상당구로 나오는 것을 확인!

 

 

맵(Map) 순회

- Hash map(키가 정렬이 되지 않아서 어떤 순서로 나올 지 알 수 없음) = 다른 언어에서는 Unodered Map이라고 함.

   Sorted Map(키가 정렬이 되어서 키-값 순으로 나옴) = 다른 언어에서도 동일하게 Sorted Map이라고 함.

- Go에서는 Hash map을 사용하고 있어서 순서가 보장되지 않음!!

package main

import "fmt"

type Product struct {
	Name  string
	Price int
}

func main() {
	m := make(map[int]Product)

	m[16] = Product{"볼펜", 500}
	m[46] = Product{"지우개", 200}
	m[78] = Product{"자", 1000}
	m[345] = Product{"샤프", 3000}
	m[897] = Product{"샤프심", 500}

	for k, v := range m {
		fmt.Println(k, v)
	}
}


// 결과 (정렬되지 않은 값이 출력)

897 {샤프심 500}
16 {볼펜 500}
46 {지우개 200}
78 {자 1000}
345 {샤프 3000}

 

 

요소 삭제와 존재 여부

- map에서 삭제하고 싶은 경우 delete() 함수로 요소를 삭제할 수 있음.

- 맵 변수와 삭제할 키 값을 차례로 넣으면 해당 요소를 맵에서 삭제함.

- 요소를 조회할 때 키에 알맞는 요소가 없으면 값 타입의 기본값을 반환함.

delete(m, key)

// m: 맵 변수
// key: 삭제 키

 

package main

import "fmt"

func main() {
	m := make(map[int]int)		// 맵 생성
	m[1] = 0			// 요소 추가
	m[2] = 2
	m[3] = 3

	delete(m, 3)			// 요소 삭제
	delete(m, 4)			// 없는 요소 삭제 시도
	fmt.Println(m[3])		// 삭제된 요솟값 출력
	fmt.Println(m[1])		// 존재하는 요솟값 출력
}


// 결과

0
0

 

package main

import "fmt"

func main() {
	m := make(map[int]int)
	m[1] = 0
	m[2] = 2
	m[3] = 3

	delete(m, 3)
	delete(m, 4)

	v, ok := m[3]
	fmt.Println(v, ok)
	v, ok = m[1]
	fmt.Println(v, ok)
}

// 결과

0 false
0 true

 

- m[3]의 값이 삭제가 되었는지알고 싶으면 값을 2개를 받아서 확인하면 됨.

- 첫 번째(v)는 값이 있으면 해당 값이 출력되고, 두 번째(ok)는 bool 타입으로 값이 있는지 없는지 출력됨.

→ 만약, v = m[3]으로 값을 하나만 받으면 v값이 3에 해당 하는 요소가 없을 때는 v값이 기본 값이 됨.

   = 원래 3에 해당 하는 값이 기본 값인지, 없어서 기본 값인지 알 수가 없음.

 

 

맵, 배열, 리스트 속도 비교

	배열, 슬라이스	리스트	맵
추가	O(N)	O(1)	O(1)
삭제	O(N)	O(1)	O(1)
읽기	O(1) - 인덱스로 접근	O(N) - 인덱스로 접근	O(1) - 키로 접근

 

- 맵은 삭제, 추가, 읽기에서 요소 개수와 상관 없이 속도가 일정하나, 키-값 쌍으로만 동작하기 때문에 인덱스를 사용할 수 없음.

   그리고, 순서가 보장되지 않으며 배열과 리스트에 비해 상대적으로 메모리를 많이 차지함.

- 배열은 추가, 삭제에서 요소 개수가 많을 수록 오래 걸리고, 리스트는 요소 읽기에서 요소 개수가 많아질 수록 오래 걸림.

 

 

맵(Map)의 원리

- 맵을 이해하기 위해서는 해시 함수(Hash Function)의 동작을 이해해야함.

- 맵을 다른 말로 해시맵 또는 해시 테이블이라고 부를 만큼 앱과 해시는 뗄 수가 없음.

 

★ 해시(Hash)

- 해시란 잘게 부순다는 뜻

1. 같은 입력이 들어오면 같은 결과가 나옴.

2. 다른 입력들이 들어오면 되도록 다른 결과가 나옴.

3. 입력 값의 범위는 무한대이고, 결과는 특정 범위를 가짐.

 

해시로 맵을 만들자!

- 해시 함수는 결괏값이 항상 일정한 범위(개수)를 가짐.

- 같은 입력에서는 같은 결과를 보장하고, 일정 범위에서 반복됨.

package main

import "fmt"

const M = 10	// 나머지 연산의 분모

func hash(d int) int {
	return d % M	// 나머지 연산
}

func main() {
	m := [M]int{}	// 값을 저장할 배열 생성

	m[hash(23)] = 10	// 키 23에 값 설정
	m[hash(259)] = 50	// 키 259에 값 설정

	fmt.Printf("%d = %d\n", 23, m[hash(23)])	// 값 출력
	fmt.Printf("%d = %d\n", 259, m[hash(259)])	// 값 출력

}


// 결과

23 = 10
259 = 50

 

// 배열 정의

var m [M]int   // M은 10

// 키 23, 값 10의 요소 추가

m[hash(23)] = 10

 

- 해시 함수 hash(23)의 결과는 23%10인 3이 반환되므로, 배열 인덱스가 3인 위치에 값 10을 대입함.

- 키-값으로 값을 읽어올 때도 hash() 함수 결과에 해당하는 인덱스의 배열값을 반환하면 됨.

 

 

해시 충돌

- 해시 함수는 다른 입력임에도 같은 결과가 낼 수 있음.

- hash(23)과 hash(33)은 (같은 위치에 저장되므로) 출력 값이 같음.

m[hash(23)] = 10
m[hash(33)] = 50   // 기존 m[hash(23)] 값이 50으로 덮어쓰여짐.

// 23 % 10 = 3
// 33 % 10 = 3

 

→ hash(23)과 hash(33) 모두 인덱스 위치가 3이므로, m[hash(23)]은 50이 되어버림 = 해시 충돌

- 이를 해결하기 위한 단순한 방법은 인덱스 위치마다 값이 아닌 리스트를 저장함.

 

 

 

- 위 처럼 리스트로 저장하면 기존 값을 보존할 수 있음.

 = 값을 읽을 때 해당 인덱스에 링크된 모든 리스트를 조사해 매칭되는 키의 값을 반환하면 해시 충돌 문제에서 벗어남.

 

✓ 해시 함수는 요소 개수와 상관 없이 고정된 시간을 갖는 함수이기 때문에 해시 함수를 사용하는 맵이 읽기, 쓰기에서 O(1)의 시간값을 갖게 됨.

     키가 크다고 해시 함수 결괏값이 커지는 게 아니기 때문에 맵은 키와 무관하고 입력 순서와도 무관한 순서로 순회하게 됨.