Map

map은 Key와 Value 형태로 데이터를 저장하는 형태이다. 대표적인 예로 전화 번호부가 있다.
key = 이름 , value = 전화번호 라고 볼 수 있다.

Dictionary나 HashTable로 불리기도 한다.

Map 구현 방법

• 배열
  Map을 구현 할때 배열로 하게 되면 특정 값을 찾을때 첫번째부터 하나 하나 비교해야 되서 O(N)으로 비효율 적인 방법이다.

• BST
  BST방법을 이용하게 된다면 O(logN)으로 효율적으로 구현 할 수 있다. 이 방법을 Sorted Map 혹은 Ordered Map 이라고 한다.

• HASH
  hash라는 함수를 이용하여 key를 입력하면 바로 value값을 뽑아주는 방법이다. 걸리는 시간은 O(1)으로 굉장히 효율적으로 Map을 구현 할 수 있다. 이 방법을 Hash Map 이라고 한다.

1. Hash 함수

*특징

• 출력 값의 범위가 정해져 있다.
• 같은 입력이면 같은 출력이 나온다.
• 다른 입력이면 다른 출력이 나오는 경우가 많다. (확정이 아님)

위의 특징을 만족시키는 것 들

1) 삼각함수 sin

입력이 무한대라도 나오는 출력 값은 -1~1**
0º = 0 , 90º = 1, 180º = 0, 270º = -1, 360º = 0,...
값이 일정한 것도 있는가 하면 다른 입력에 다른 출력이 나오는 경우도 있다.

2) 나머지(Modular) 연산

0 ~ ∞ % 12 을 했을때 출력 값이 0 ~ 11을 반복 하는것을 볼 수 있다. 항상 같은 출력 값도 가지고 다른 입력에 다른 출력 값도 가진다.

sin함수는 복잡하고 정수를 넣으면 실수가 나온다. 하지만 나머지 연산은 간단하고 정수를 넣으면 정수가 나온다는 장점이 있다.

3) one-way function

N x 3 = 9 라는 식이 있을때 우리는 이 N을 3이라는것을 알 수 있다. 그 이유는 x의 반대 연산인 ÷ 가 있기 때문이다. 이러한 특징을 two-way function 이라 한다.

하지만 나머지(Modular) 연산의 출력값을 보고 입력값을 찾아내는건 경우의 수가 무한대이기 때문에 어렵다. 예를 들어 N % 12 = 3 이라고 했을 때 N은 3, 15, 27,...∞ 이다. 이러한 연산을 one-way function 이라고 부른다.

이러한 특징을 이용하여 hash 함수는 암호화에 자주 사용된다.

Rolling Hash 구현

문자열이 s0 ~ sN 있을 때
s0의 해쉬 값 h0 = (h0-1 x a + s0) % b
s1의 해쉬 값 h1 = (h0 x a + s1) % b
s2의 해쉬 값 h2 = (h1 x a + s2) % b
...
이런 형식으로 해쉬값을 구해나 가는 것을 Rolling Hash 라고 한다.

이 때 한 문자열당 1byte 이므로 0 ~255 까지의 숫자가 구현 될 수 있다. 그렇기 때문에 a의 값은 '+ si' 보다 큰 값 256 정도로 지정해 준다.

b의 값은 소수(자신 이외의 자연수로는 나눌 수 없는, 1보다 큰 자연수)로 정해 주는것이 좋다.
소수를 사용하면 값의 분포도가 넓게 퍼진다.
예) 3571

ex) Rolling Hash package

package dataStruct

func Hash(s string) int {
	h := 0
	a := 256
	b := 3571
	for i := 0; i < len(s); i++ {
		h = (h*a + int(s[i])) % b
	}
	return h
}

ex) Rolling Hash main

package main

import (
	"Golesson/dataStruct"
	"fmt"
)

func main() {
	// 같은 값을 입력했을 경우
	fmt.Println("abcde =", dataStruct.Hash("abcde"))
	fmt.Println("abcde =", dataStruct.Hash("abcde"))

	// 다른 값을 입력했을 경우
	fmt.Println("abcdf =", dataStruct.Hash("abcdf"))

	// 입력 값이 길 경우
	fmt.Println("tbcdfdhdghddhd =", dataStruct.Hash("tbcdfdhdghddhd"))
}
---------------------------------
abcde = 2598
abcde = 2598  // 같음
abcdf = 2599  // 달라짐
tbcdfdhdghddhd = 1892 // 3571 범위 안

Hash Map 구현

구현 방법

1. 0 ~ 3570 의 인덱스를 가지는 배열을 만든다.
2. key 값으로 문자열을 받으면 hash 함수에 넣는다.
3. hash 함수를 통해 나온 값에 해당하는 인덱스에 value값을 저장
4. key 로 조회 했을 경우 같은 hash 값을 가지는 인덱스의 value를 반환

• 문제점
  입력의 범위는 무한대 이지만 출력의 범위는 0 ~ 3570 까지 이다. 무한대의 입력이 들어왔을 때 출력이 유한대라면 정보는 손실 되고 이 것을 손실 압축 이라고 한다. 손실 압축에 경우 출력을 가지고 입력을 복원 할 수 없다(one-way fuction).
  
  또한 다른입력에서 같은 값(hash 충돌)이 나올 수 있다.
  즉 key AAA 와 key BBB 가 같은 hash 값을 가질 수 있다.
  
  이 점을 방지 하기위해 각 각의 인덱스에 배열을 하나 더 만든다. 다른 입력에 같은 hash값이 나왔을 경우 같은 인덱스안에서 나눠서 저장한 다음 value를 찾는 방법이 있다.

ex) Hash Map package

package dataStruct

func Hash(s string) int {
	h := 0
	a := 256
	b := 3571
	for i := 0; i < len(s); i++ {
		h = (h*a + int(s[i])) % b
	}
	return h
}

type keyValue struct {
	key   string
	value string
}

type Map struct {
	keyArray [3571][]keyValue
	// 0 ~ 3570 만큼의 배열의 각 인덱스에 key와 value 값을 갖는 list를 만든다.
}

func (m *Map) Add(key, value string) {
	h := Hash(key) // key에 대한 hash값
	m.keyArray[h] = append(m.keyArray[h], keyValue{key, value})
	// key의 hash값에 해당하는 인덱스에 key와 value를 가지는 리스트를 집어 넣음
}

// map을 만드는 함수
func CreatMap() *Map {
	return &Map{}
}

// key에 대한 value를 가져오는 함수
func (m *Map) Get(key string) string {
	h := Hash(key)
	for i := 0; i < len(m.keyArray[h]); i++ {
		if m.keyArray[h][i].key == key {
			return m.keyArray[h][i].value
		} // 현재 hash 값안의 리스트 에서 그 길이 만큼 돌아서 value를 찾는다.
	}
	return "" //없으면 빈값을 반환
}

ex) Hash Map main

package main

import (
	"Golesson/dataStruct"
	"fmt"
)

func main() {
	m := dataStruct.CreatMap()
	m.Add("AAA", "01012345789")
	m.Add("BBB", "01055555555")
	m.Add("asdfsdff", "01099999999")
	m.Add("CCC", "010987654321")

	fmt.Println("AAA =", m.Get("AAA"))
	fmt.Println("CCC =", m.Get("CCC"))
	fmt.Println("DDD =", m.Get("DDD"))
	fmt.Println("asdfsdff =", m.Get("asdfsdff"))

}
-----------------------------
AAA = 01012345789
CCC = 010987654321
DDD =
asdfsdff = 01099999999

Hash Map

• 장점: find, add, remove 모두 다 O(1)로 빠르다.
• 단점: hash값에는 순서가 없기 때문에 정렬을 할 수가 없다.

Golang Map

go언어 에서는 기본적으로 map을 제공하고 있어서 직접 만들필요 없이 사용 가능하다.

1. map 선언 하기

var변수명 map[key타입]value타입
var m map[string]string

ex1)

package main

import (
	"fmt"
)

func main() {
	var m map[string]string
	// 선언만 한다고 바로 쓸 수 없음
	m = make(map[string]string)
	// 초기화를 해줘야 됨

	m["abc"] = "bbb"
	fmt.Println(m["abc"])

	m1 := make(map[int]string)
	// 선언 초기화
	m1[53] = "ddd"
	fmt.Println(m1[53])

	fmt.Println("m1[55] =", m1[55])
	//없는 값을 입력할 경우 string의 default값 빈 문자열을 반환한다.

	m2 := make(map[int]int)
	m2[4] = 4

	fmt.Println("m2[10] =", m1[10])
	// int향의 default 값 0을 반환

	m3 := make(map[int]bool)
	// bool 형의 경우 설정된 값은 true 설정이 안된 값은 false
	m3[4] = true

	fmt.Println(m3[6], m3[4])
}
---------------------------
bbb
ddd
m1[55] =
m2[10] =
false true

설정을 안한 값은 default 값이 나온다고 한다면 만약 int형의 map에 0을 저장했을때 그게 default 값인지 내가 초기화한 값인지를 어떻게 구별 할 수 있을까?

ex2)

package main

import (
	"fmt"
)

func main() {
	m2 := make(map[int]int)
	m2[4] = 4
    	m2[5] = 0

	v, ok := m2[5]
	v1 := m2[4]
	v2, ok1 := m2[10]
    	// go map에서는 해당값이 있는지 없는지 확인 하기 위해 bool형 값을 동시에 반환해 준다.

    	fmt.Println(v, ok)
	fmt.Println(v1)
	fmt.Println(v2, ok1)
}
-----------------------------------
0 true // 존재하는 값
4
0 false // default 값
    

2. 삭제하기

ex3) delete

package main

import (
	"fmt"
)

func main() {
	m2 := make(map[int]int)
	m2[4] = 4
    	m2[5] = 0

	v, ok := m2[5]
	v1 := m2[4]
	v2, ok1 := m2[10]

    	fmt.Println(v, ok)
	fmt.Println(v1)
	fmt.Println(v2, ok1)
    
    delete(m2, 5)
	// 지우고 싶은 map의 key값을 입력
	v, ok = m2[5]

	fmt.Println(v, ok)
	fmt.Println(v1)
	fmt.Println(v2, ok1)
}
----------------------------------
0 true
4
0 false

0 false // m2[5] 가 삭제됨
4
0 false
    

3. 순회하기

ex3) for range

package main

import (
	"fmt"
)

func main() {
	m2 := make(map[int]int)
	m2[4] = 4
    	m2[5] = 0
	m2[2] = 2
	m2[10] = 10
	m2[8] = 8
    	for key, value := range m2 {
        // m2의 모든 항목을 돌면서 key, value를 반환 한다.
		fmt.Println(key, "=", value)
	}

}