Golang #1 - Map

Golang #1 - Map

Map 

map은 Golang의 Built-in 데이터 타입이며 Key/Value의 구조를 지닌 Hash table을 구현한 자료구조입니다. Hash table을 구현하는 많은 방법들이 있고, 이들마다 조금씩은 다르겠지만 Fast Lookups, Add, Delete라는 특징을 공통으로 가지고 있는 자료구조입니다.

 

Hash Table

Golang의 Hash Table인 'map'을 알아보기 전에, 우선 Hash Table이 어떤 것인지부터 알아보려고 합니다. Hash Table은 각각의 Key 값에 Hash Function이라는 간단한 함수를 적용하여 배열의 고유한 Index를 생성하고, 생성된 Index를 통해 Value를 저장하는 자료구조의 형태입니다.

 

Hash Function을 사용하여 고유한 Index를 만든다는 것은, Key를 통해 Value를 찾을 때도 Hash Function이라는 간단한 함수를 사용해 Lookup할 수 있다는 뜻입니다. 따라서 Key에 따른 Value를 찾기 위한 시간 복잡도는 O(1)에 가깝습니다. Value를 찾기 위해서 Hash Function을 딱 한 번만 수행하면 되니까요. 물론, 무수히 많은 Key들을 유한한 개수의 Hash Value(=Index)에 매핑함으로써 간혹 서로 다른 문자열(=Key)이 Hash Function을 통해 Hashing된 결과가 중복되는 경우가 있습니다. 이를 Collision이라고 부르며, 충돌 문제를 해결하기 위해 다양한 아이디어가 있겠지만, 간단하게 해당 Index에 Array의 형태로 추가시키는 방법이 있습니다. 하단의 그림처럼 말이죠. 이러한 경우에는 탐색의 시간 복잡도가 O(1)이 아닌, O(n)으로 증가하게 됩니다. 그래서 충돌을 줄여줄 수 있는 좋은 Hash Function을 사용하는 것이 좋습니다.



Hash Table을 사용하는 이유는 다음과 같습니다. 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있습니다. 무수히 많은 값을 유한한 개수의 Hash Value에 매핑함으로써 말이죠. 또한, 고유한 위치를 가졌기에 검색이나 삽입, 삭제 시 빠르다는 장점이 있습니다. 추가적으로, Key와 Hash Value 사이에 직접적인 연관성이 없어 보안에도 사용됩니다. 보안에 사용하는 Hash Function으로는 MD5, SHA 등이 있죠. 블록체인을 구성하는 기본적인 기술도 Hashing입니다.

 

간단한 Hash Function으로 고유의 Index를 Golang으로 만들어본다면 다음과 같습니다. Hashing이라는 Function을 통해 고유의 Index를 만들고 배열에 그 값을 저장하는 형태입니다. 정말 간단한 형태라 어떤 느낌인지만 보면 될 것 같습니다.

func Hashing(s string) int {
	h:= 0
    
    for i :=0; i < len(s); i++ {
		h = int(s[i]) + h
    }
    
    h = h % 7
    
    fmt.Println(h)
}

func main() {

  fmt.Println(Hashing("Harry"))   // 0
  fmt.Println(Hashing("Smith"))   // 6
  fmt.Println(Hashing("Andrew"))  // 2
  
  map[0] = "010-1111-1111" // Harry
  map[6] = "010-2222-2222" // Smith
  map[2] = "010-3333-3333" // Andrew
    
}

 

About Map

이제 정말 map에 대해 알아보도록 합시다. 정확히 어떤 Hash Table으로 구현되었는지는 알 수 없지만, 암튼 map은 Hash Table로 만들어진 데이터 타입입니다. map을 만들기 위해서는 다음과 같이 key와 value의 타입을 정해 선언합니다.

var m  map[key_type]value_type

var m1 map[int]string
var m2 map[string]bool

 

여기서 중요한 것은 map은 Reference Type이기에 초기 선언된 map은 nil 값을 가집니다. nil map에는 어떤 데이터도 쓸 수 없는 상태이기에 선언한 map을 Initialize해주는 작업이 필요합니다. map을 Initialize해주기 위해서는 make 함수를 사용할 수도 있고, 단순히 '{}' 를 붙여서 initialize해줄 수 있습니다. 만약 Initialize 작업을 해주지 않는다면 Runtime error가 나오기에 꼭 하도록 합시다.

func main() {
	// func 내부에서만 변수선언 축약문 사용 가능
	m1 := make(map[string]int)
	m2 := map[string]int{}
}

 

Golang의 map에서는 약간 특이한 점이 있다. Key를 바탕으로 값을 출력할 때 두 가지 값을 반환한다는 점이다. 첫 번째 반환값은 Value이며, 두 번째 반환값은 해당 Key에 해당하는 값이 존재하는지 여부를 체크해주는 값이다. 또한, 해당하는 Key가 없을 경우에는 첫 번째 반환값인 Value가 Zero Value로 출력된다는 점인데, 예를 들어, Value의 Type이 Int일 경우에는 0이 출력되고, String 타입일 경우에는 아무런 문자도 출력되지 않는다. 엄밀히 말하자면 0의 길이를 가지는 String(="")이 출력된다. 그래서 값이 있는지 체크해줄 때는 꼭 두 번째 반환값을 통해 확인해주는 것이 좋다. 정말 Value가 0이거나 ""인 경우가 있을 수도 있으니 말이다.

func main() {

  m := make(map[int]int)

  m[1] = 1

  mValue1, mCheck1 := m[1]
  mValue2, mCheck2 := m[2]

  fmt.Println(mValue1, mCheck1) // 1, true
  fmt.Println(mValue2, mCheck2) // 0, false

}

 

간혹 하단의 구조처럼 map 안에 map을 넣어주는 Nested 형태의 구조가 생길 수도 있는데, 위에서 말했던 것처럼 각각의 map을 Initialize해줘야 하는 작업이 필요하다. Golang의 공식문서에서는 다음과 같이 Add Function으로 Inner map을 우선 Initialize해주어 할당하는 예시를 들어주고 있는데, 사실 map을 중첩으로 사용하기보다는 struct 구조를 사용해 복잡성을 해소하는게 더 낫다. 

hits := make(map[string]map[string]int)

// inner map init
hits_inner := make(map[string]int)
hits["path"] = hits_inner


// Golang Doc
func add(m map[string]map[string]int, path, country string) {
    mm, ok := m[path]
    if !ok {
        mm = make(map[string]int)
        m[path] = mm
    }
    mm[country]++
}
add(hits, "/doc/", "au")

 

마지막 참고할 점 몇가지를 이야기하자면, 1) map의 Value는 Addressable하지 않다. 즉, map 자체는 Memory Address를 가지지만 map 안에 Key/Value 형태로 저장되어 있는 값은 Address를 가지지 않는다. 이미 내부적으로 Hash Function에 의한 Address를 가지고 있기 때문이다. 2) 간혹 map과 array의 색인 속도를 비교해야할 때가 있는데, Int 타입이냐 String 타입이냐에 따라 속도가 다를 수도 있지만, 대개 수가 적을 때 array가 빠르고 수가 많을 때는 map이 빠르다. 이는 해당 자료구조의 특징들 때문인데 map의 경우 O(1) 복잡도라 값이 많아지더라도 일정시간만큼 걸리고, array는 형태에 따라서 다르겠지만 O(n) 정도의 시간복잡도가 소요됩니다.

 

참고자료

- Golang Map, Golang Doc

- 컴맹을 위한 Go언어 프로그래밍 기초 강좌, Tucker

- 해싱, 해시함수, 해시테이블, ratsgo's blog

- Golang pointer to map value, xspdf

- Go: Slice search vs Map lookup, Graham King