GoベースMap, Hash

6937 ワード
テキストリンク

Map


mapは、KeyとValue形式でデータを格納する形式である.典型的な例は電話帳です.
key=名前、value=電話番号.
DictionaryまたはHashTableとも呼ばれる.

Mapの実装方法


  • 整列
    マップを実装するときに配列を使用する場合、特定の値を検索するときは、最初から1つずつ比較する必要があるため、O(N)を使用するのは無効な方法です.

  • BST
    BST法を用いる場合,O(logN)を用いて効率的に実施できる.この方法をSordMapまたはOrdered Mapと呼ぶ.

  • HASH
    hashという関数を使用してkeyを入力すると、値を抽出する方法になります.所要時間はO(1)であり,非常に効率的にMapを実現できる.この方法をHash Mapといいます.

    • 1.Hash関数


    *機能
  • 出力値の範囲が設定されています.
    • 入力が
  • の場合、出力は同じです.
  • 他の入力では、異なる出力が出ることが多いです.(不確定)
    • 上記の特徴を満たすもの.

    1）三角関数sin



    入力が無限であっても、出力値は-1~1**
    0º = 0 , 90º = 1, 180º = 0, 270º = -1, 360º = 0,...
    一定の値があり、異なる入出力もあります.

    2）剰余（モジュール化）演算



    0~∞%12とすると、出力値が0~11繰り返すことがわかる.常に同じ出力値があり、異なる入出力値もあります.
    sin関数は複雑で、整数を加えるとエラーが発生します.しかし、残りの演算は簡単で、整数を入れると整数が発生します.

    3) one-way function


    n x 3=9のとき,このnは3であることが分かった.これは、xには反対の演算、すなわち「|」があるからである.この特徴を双方向関数と呼ぶ.
    ただし、残り(モジュール化)演算の出力値を表示することで入力値を見つけるのは難しい.その数は無限であるからである.例えば、N%12=3の場合、Nは3,15,27.である.∞です.この演算をone-way関数と呼ぶ.
    これらの特徴を用いてhash関数は暗号化によく用いられる.

    Rolling Hash実施



    文字列s 0~sNの場合
    s 0のハッシュ値h 0=(h 0-1 xa+s 0)%b
    s 1のハッシュ値h 1=(h 0 xa+s 1)%b
    s 2のハッシュ値h 2=(h 1 x a+s 2)%b
    ...
    このような形でハッシュ値を求めることをRollingハッシュと呼ぶ.
    このとき、各文字列は10バイトで、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実装


    実施方法

  • 0～3570インデックスの配列を作成します.
  • キー値で文字列を受信するとhash関数に格納されます.
  • ハッシュ関数は、導出値
    • に対応するインデックスに値を格納する.
  • キーでクエリーを実行すると、同じハッシュ値を持つインデックスの値
    • が返されます.
  • 問題
    入力の範囲は無限ですが、出力の範囲は0から3570です.入力が無限大の場合、出力が限られている場合、損失圧縮と呼ばれる情報が失われます.損失圧縮の場合、出力復元入力(一方向関数)は使用できません.
    また、他の入力では同じ値(hash競合)が発生する可能性があります.
    すなわち、key AAAおよびkey BBBは、同じhash値を有することができる.
    これを防ぐために、各インデックスに配列をもう1つ作成します.別の入力に同じ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)より速い.
    • 欠点:ハッシュ値に順序がなく、ソートできません.

    Golang Map


    go言語は基本的にmapを提供しており、自分で作成する必要はありません.

    1.宣言マッピング

    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)
	}

}
    Netty 4ソース分析-Bootstrap
    [TIL] Connection Pool