python 간단 한 hashmap 구현

python 은 간단 한 hashmap 를 실현 합 니 다. 엄밀 하지 않 고 문제 가 있 는 점 을 많이 지적 해 주 십시오.
최근 데이터 구 조 를 뒤 져 보 니 자신 에 대한 지식 이 부족 하고 자신의 기록 이 라 고 할 수 있 으 며 데이터 구 조 를 공부 하고 있 는 늙 은 철 들 에 게 공유 하고 함께 공부 하고 싶 습 니 다.
원리 python 언어 중의 dict 바 텀 은 hashmap 구 조 를 바탕 으로 이 루어 진 것 이 므 로 dict 의 사용 은 말 하지 않 겠 습 니 다.관건 은 hashmap 가 한 무더기 의 데이터 에서 키 에 따라 value 를 찾 을 수 있다 는 것 이다. 이 관건 은 주로 hash 함수 에 의 해 이 루어 진다.상세 한 원 리 는 라 는 책의 8.9 장 을 보 세 요. 저 는 잘 말 한 것 같 습 니 다.
간단하게 구 조 를 실현 하 는 책 에서 주로 C 언어 로 hashmap 구 조 를 실현 합 니 다. 다음은 python 언어 로 이 루어 진 코드 를 드 리 겠 습 니 다.그리고 hash 충돌 문 제 를 해결 하기 위해 저 는 '체인 주소 법' 의 구 조 를 사 용 했 습 니 다.MyHash 내 부 는 items 목록 을 사용 하여 데 이 터 를 저장 합 니 다. items 는 하나의 목록 이 고 모든 요소 도 하나의 목록 입 니 다. 요소 목록 에 구체 적 인 (key, value) 원 그룹 이 저장 되 어 있 습 니 다. 서로 다른 key 는 hash 함수 에 따라 index 를 먼저 계산 합 니 다. 즉, 어느 목록 에 저장 되 어 있 는 지, 삽입 할 때 직접 append 입 니 다.찾 을 때 equals 방법 에 따라 찾 아야 할 key 와 목록 에 있 는 모든 원 그룹의 첫 번 째 값 (key) 을 비교 하고, 같은 값 을 찾 으 면 원 그룹의 두 번 째 값 (value) 을 되 돌려 주 며, 찾 지 못 하면 raise KeyError 이상 을 찾 습 니 다.

# coding=utf-8


class MyHash(object):

    def __init__(self, length=10):
        self.length = length
        self.items = [[] for i in range(self.length)]

    def hash(self, key):
        """   key items  list ，       key     """
        return key % self.length

    def equals(self, key1, key2):
        """    key    ，       key     """
        return key1 == key2

    def insert(self, key, value):
        index = self.hash(key)
        if self.items[index]:
            for item in self.items[index]:
                if self.equals(key, item[0]):
                    #          key，       （  value）
                    self.items[index].remove(item)
                    break
        self.items[index].append((key, value))
        return True

    def get(self, key):
        index = self.hash(key)
        if self.items[index]:
            for item in self.items[index]:
                if self.equals(key, item[0]):
                    return item[1]
        #    key，   KeyError  
        raise KeyError

    def __setitem__(self, key, value):
        """    myhash[1] = 30000     """
        return self.insert(key, value)

    def __getitem__(self, key):
        """    myhash[1]     """    
        return self.get(key)


myhash = MyHash()
myhash[1] = 30000
myhash.insert(2, 2100)
print myhash.get(1)
myhash.insert(1, 3)
print myhash.get(2)
print myhash.get(1)
print myhash[1]

몇 시

이상 키 만 int 형식 으로 지원 하 는 경우, 다른 유형의 키 를 지원 하려 면 hash 방법 및 equals 방법

을 다시 실현 해 야 합 니 다.

삽입, 읽 기 방법 만 실 현 했 고 다른 방법 은 python 에서 dict 의 인터페이스 방법 에 따라 추가 할 수 있 습 니 다

setitem, getitem 방법 을 실현 하여 우리 의 대상 도 dict 처럼 추가, 읽 을 수 있 도록 합 니 다