Go 언어 프로그래밍 - 자료구조 - 2

『Tucker의 Go 언어 프로그래밍』 스터디 요약 노트입니다.

---

맵(map)

키와 값 현태로 데이터를 저장하는 자료구조이다.

프로그래밍 언어에 따라서 딕셔너리(dictionary), 해쉬 테이블(hash table), 해쉬맵(hash map) 등으로 부른다.

같은 키를 여러번 작성하면 해당 키에 매핑되는 값이 업데이트된다.

map[key]value

map[키 타입]값 타입

맵은 생성 시, make를 이용하여 초기화가 필요하다.

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["백두산"])
}

맵 순회

HashMap (= Unordered Map) : 정렬되지 않음

Shorted Map : 키값을 기준으로 정렬

go 언어에서 맵은 hashmap 이기 때문에, 순서가 정렬되지 않는다.

package main

import (
	"fmt"
)

type Product struct {
	Name  string
	Price int
}

func main() {
	//맵을 생성하기 위한 초기화
	m := make(map[int]Product)

	m[16] = Product{"pen", 500}

	m[46] = Product{"eraser", 500}
	m[78] = Product{"ruler", 200}
	m[345] = Product{"sharp", 1000}
	m[897] = Product{"sharp core", 500}

	//삽입 순서가 유지되지 않는다.
	for k, v := range m {
		fmt.Println(k, v)
	}
}

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] //값과 bool 값을 같이 받아 확인 가능하다.
	fmt.Println(v, ok)
	fmt.Println(m[1])
}

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

맵의 원리

해쉬 함수 동작 이해 => 해쉬란 잘게 부순다는 뜻이다.

1. 같은 입력이 들어오면 같은 결과가 나온다.
2. 다른 입력이 들어오면 되도록 다른 결과가 나온다.
3. 입력값의 범위는 무한대이고 결과는 특정 범위를 갖는다.

일반적으로 나머지 연산(modular)을 주로 사용한다.

 

해쉬로 맵을 만들어보자

package main

import (
	"fmt"
)

const M = 10

//해쉬 함수를 생성
func hash(d int) int {
	//modular 연산
	return d % M
}

func main() {
	m := [M]string{}

	//해시함수로 맵 정의
	//일정한 속도로 조회 가능
	m[hash(23)] = "송하나"
	m[hash(259)] = "백두산"

	fmt.Printf("%d = %s\n", 23, m[hash(23)])
	fmt.Printf("%d = %s\n", 259, m[hash(259)])
}

해쉬 충돌

modular 연산(나머지 연산)을 통해 해쉬를 만들 경우, 해쉬 충돌이 일어날 수 있다.(배열 길이가 10일 경우, 기값이 23과 33의 값이 같다.)

이를 회피하기 위해 각 값을 리스트로 가지게 된다.

해쉬의 쓰임새

File checksum (주로 파일/계정 등 데이터 변조여부 확인)

암호화 : 해쉬의 일방향 특징 활용 등

 

 

참고

Tucker의 Go언어 프로그래밍 - Go가 온당(22장)

https://www.youtube.com/c/TuckerProgramming/videos