go 해시 표 - map 의 간단 한 실현

7336 단어
해시 시계
  • 해시 표 가 뭐 예요?
  • 산 목록 (Hash table, 해시 표 라 고도 함) 은 키 코드 값 (Key value) 에 따라 직접 접근 하 는 데이터 구조 입 니 다.즉, 키 코드 값 을 표 의 한 위치 에 비 추어 기록 에 접근 함으로써 검색 속 도 를 빠르게 하 는 것 이다.이 매 핑 함 수 는 해시 함수 라 고 하 는데 기록 을 저장 하 는 배열 을 산 목록 이 라 고 합 니 다.
  • 주어진 표 M, 함수 f (key) 가 존재 합 니 다. 주어진 키워드 값 key 를 함수 에 대 입 한 후 이 키 워드 를 포함 한 표 에 기 록 된 주 소 를 얻 을 수 있다 면 표 M 을 해시 (Hash) 표 라 고 하고 함수 f (key) 를 해시 (Hash) 함수 라 고 합 니 다.
  • 그게 하 쉬 가 뭐야?
  • Hash 는 보통 하나의 정수 로 특정한 알고리즘 을 통 해 하나의 문자열 을 하나의 정수 로 압축 할 수 있 습 니 다. 이 수 는 Hash, 흔히 볼 수 있 는 MD5, SHA 1 등
    • 이 라 고 합 니 다.
  • 여기 서 알 수 있 듯 이 우리 가 자주 사용 하 는 map 나 dictionary 는 모두 하 쉬 표 의 관계
    • 에 속한다.
  • 그럼 간단하게 이 루어 보도 록 하 겠 습 니 다. 간단 한 맵
    • 지퍼 법 (체인 주소 법)
  • 절 차 를 설명 하기 전에 왜 다른 것 이 아니 라 지퍼 법 을 사용 해 야 하 는 지 먼저 말 해 보 세 요.
  • 우선 지퍼 법의 학습 은 배열 과 링크 의 지식 만 있 으 면 된다
  • 그 다음으로 지퍼 법 은 하 쉬 표 충돌 을 간단하게 해결 했다
    • .
  • 그 특징:
  • 배열 의 특징 은 주소 찾기 가 쉽 고 삽입 과 삭제 가 어렵 다 는 것 이다.
  • 링크 의 특징 은 주소 찾기 가 어렵 고 삽입 과 삭제 가 쉽다 는 것 이다.
  • 그래서 하 쉬 리 지퍼 법 은 주 소 를 찾기 쉽 고 삽입 삭제 가 간단 하 다
    • .

    실현 절차
  • //1.       
type MpNode struct {
 Data Dict    //            k v     
 Next *MpNode //     
}
type Dict struct {
 Key   string
 Value interface{}
}

    //2    
//         
func newNodeHead() *MpNode {
 node := new(MpNode)
 node.Data.Key = " key"
 node.Data.Value = " value"
 node.Next = nil
 return node
}

    //   
//3          
//   key value     
func (node *MpNode) data(k string, v interface{}) *MpNode {
 if node == nil {
     node = newNodeHead()
 }
 node.Data.Key = k
 node.Data.Value = v
 return node
}

    //4             
func (node *MpNode) add(k string, v interface{}) {
 //     k        key                              
 if node.getKey(k) != nil {
     return
 }
 //      
 for node.Next != nil {
     node = node.Next
 }
 //        
 node.Next = node.Next.data(k, v)
}

    • 여기까지 우 리 는 싱글 체인 에 key, value 값 을 저장 하 는 것 을 초보 적 으로 실현 했다.
  • //5             
func MpDemo() {
  node := newNodeHead()
  node.add("1", "2")
  node.add("2", 3)
  node.Log()//   
  fmt.Println(node.Length())
}


    //6                    
func (node *MpNode) Log() {
  if node.Next == nil {
      return
  }
  fmt.Println(node.Next.Data)
  node.Next.Log()
}

    // 7                      
func (node *MpNode) Length() int {
   if node == nil {
      return 0
   }
   i := 0
   for node.Next != nil {
      i++
      node = node.Next
   }
   return i
}

    //8                 
//       
var Arr [16]*MpNode

    //9       
func NewHash() {
   for i := 0; i < 16; i++ {
      Arr[i] = newNodeHead()
   }
}

    //     
//10     key 
func SetKey(k string, v interface{}) {
   //  k                    
   num := hashNum(k)
   Arr[num].add(k, v)
}
    = = 여기 서 알 게 될 것 이다. 어, 해시 알고리즘 은 어떻게 쓰 느 냐? 그래서 나 는 간단 하고 손 으로 찢 을 수 있 는 알고리즘 을 찾 았 다. = 
    //11   16       
func hashNum(key string) int {
   var index int = 0
   index = int(key[0])
   //         
   for k := 0; k < len(key); k++ {
      index *= (1103515245 + int(key[k]))
   }
   //    2^27                          
   index >>= 27
   //   &       32    32-1           index  1111   &    15       11111    31    
   index &= 16 - 1

   return index
}

    //12   key value
func (node *MpNode) getKey(k string) interface{} {
   if node.Next == nil {
      return nil
   }
   for node.Next != nil {
      if node.Next.Data.Key == k {
         return node.Next.Data.Value
      } else {
         node = node.Next
      }
   }
   return nil
}
//13   valve key                                       
//func (node *MpNode) getValue(v interface{}) string {
//    if node.Next == nil {
//        return ""
//    }
//    for node.Next != nil {
//        if node.Next.Data.Value == v {
//            return node.Next.Data.Key
//        } else {
//            node = node.Next
//        }
//    }
//    return ""
//}

    //14  key 
func GetKey(k string) interface{} {
   num := hashNum(k)
   return Arr[num].getKey(k)
}
    이 맵 을 실행 하 세 요!
  • 우선 전체 알고리즘 은 포장 등 여러 가지 요 소 를 고려 하고 대외 적 으로 3 가지 방법 만 포함한다.
  • NewHash 에서 해시 테이블 만 들 기
  • SetKey 메모리 키 쌍
  • GetKey 키 쌍
  • 전체 코드 첨부 
  • package data

import "fmt"

//1.       
type MpNode struct {
   Data Dict    //            k v     
   Next *MpNode //     
}
type Dict struct {
   Key   string
   Value interface{}
}

//8                 
//       
var Arr [16]*MpNode

//2    
//         
func newNodeHead() *MpNode {
   node := new(MpNode)
   node.Data.Key = " key"
   node.Data.Value = " value"
   node.Next = nil
   return node
}

//9       
func NewHash() {
   for i := 0; i < 16; i++ {
      Arr[i] = newNodeHead()
   }
}

//   
//3          
//   key value     
func (node *MpNode) data(k string, v interface{}) *MpNode {
   if node == nil {
      node = newNodeHead()
   }
   node.Data.Key = k
   node.Data.Value = v
   return node
}

//12   key value
func (node *MpNode) getKey(k string) interface{} {
   if node.Next == nil {
      return nil
   }
   for node.Next != nil {
      if node.Next.Data.Key == k {
         return node.Next.Data.Value
      } else {
         node = node.Next
      }
   }
   return nil
}

//13   valve key                                       
//func (node *MpNode) getValue(v interface{}) string {
// if node.Next == nil {
//    return ""
// }
// for node.Next != nil {
//    if node.Next.Data.Value == v {
//       return node.Next.Data.Key
//    } else {
//       node = node.Next
//    }
// }
// return ""
//}

//4             
func (node *MpNode) add(k string, v interface{}) {
   //     k        key                              
   if node.getKey(k) != nil {
      return
   }
   //      
   for node.Next != nil {
      node = node.Next
   }
   //        
   node.Next = node.Next.data(k, v)
}

//6                    
func (node *MpNode) Log() {
   if node.Next == nil {
      return
   }
   fmt.Println(node.Next.Data)
   node.Next.Log()
}

// 7                      
func (node *MpNode) Length() int {
   if node == nil {
      return 0
   }
   i := 0
   for node.Next != nil {
      i++
      node = node.Next
   }
   return i
}

//     
//10     key 
func SetKey(k string, v interface{}) {
   //  k                    
   num := hashNum(k)
   Arr[num].add(k, v)
}
//14  key 
func GetKey(k string) interface{} {
   num := hashNum(k)
   return Arr[num].getKey(k)
}

//11   16       
func hashNum(key string) int {
   var index int = 0
   index = int(key[0])
   //         
   for k := 0; k < len(key); k++ {
      index *= (1103515245 + int(key[k]))
   }
   //    2^27                          
   index >>= 27
   //   &       32    32-1           index  1111   &    15       11111    31    
   index &= 16 - 1

   return index
}

//5             
func MpDemo() {
   //node := newNodeHead()
   //node.add("1", "2")
   //node.add("2", 3)
   //node.Log()
   //fmt.Println(node.Length())
}
    • 스 택 과 대기 열 설명 및 구현
    프로그램 설계 시작 4개월 G검정 합격 시 필기

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage