다양한 방법으로 해시맵 구현

문제 설명: get, set 및 remove 메소드를 사용하여 해시 맵을 구현하십시오.



난이도: 쉬움



테스트 케이스


  • 가져오기
  • 가져오기 - 키가 있음 --> 값
  • 가져오기 - 키가 존재하지 않음 --> 키 오류

  • 세트
  • 설정 - 키가 있음 --> 값 덮어쓰기
  • 설정 - 키가 존재하지 않음 --> 새 키, 값

  • 제거
  • 제거 - 키가 있음 --> 키, 값 삭제
  • 제거 - 키가 존재하지 않음 --> 키 오류


  • 연산



  • 해시 함수
  • 리턴 키 모듈로(%) 테이블 크기


  • 함수 가져오기
  • 조회를 위해 hashIndex 가져오기
  • 키가 있으면 값을 반환합니다
  • .
  • 그렇지 않으면 키 오류


  • 기능 설정
  • 조회를 위해 hashIndex 가져오기
  • 키가 있는 경우 값을 덮어씁니다
  • .
  • 그렇지 않으면 값을 추가하십시오


  • 기능 제거
  • 조회를 위해 hashIndex 가져오기
  • 키가 있는 경우 테이블에서 항목을 삭제합니다
  • .
  • 그렇지 않으면 키 오류


  • 시간 및 공간 복잡성


  • 해시 함수
  • 시간 복잡도: O(1)
  • 공간 복잡도: O(1)

  • 함수 가져오기
  • 시간 복잡도: O(1) 평균 및 최상의 경우, O(n) 최악의 경우
  • 공간 복잡도: O(1)

  • 기능 설정
  • 시간 복잡도: O(1) 평균 및 최상의 경우, O(n) 최악의 경우
  • 공간 복잡도: O(1)

  • 제거 기능
  • 시간 복잡도: O(1) 평균 및 최상의 경우, O(n) 최악의 경우
  • 공간 복잡도: O(1)




  • 암호



    class Item(object):
        def __init__(self, key, value):
            self.key = key
            self.value = value
    
    
    class HashTable(object):
        def __init__(self, size):
            self.size = size
            self.table = [[] for _ in range(self.size)]
    
        def hashFunction(self, key):
            return key % self.size
    
        def set(self, key, value):
            hashIndex = self.hashFunction(key)
            for item in self.table[hashIndex]:
                if item.key == key:
                    item.value = value
                    return
            self.table[hashIndex].append(Item(key, value))
    
        def get(self, key):
            hashIndex = self.hashFunction(key)
            for item in self.table[hashIndex]:
                if item.key == key:
                    return item.value
            raise KeyError('Key not found')
    
        def remove(self, key):
            hashIndex = self.hashFunction(key)
            for index, item in enumerate(self.table[hashIndex]):
                if item.key == key:
                    del self.table[hashIndex][index]
                    return
            raise KeyError('Key not found')
    

    단위 테스트



    import unittest
    from hashmap import HashTable
    
    
    class TestHashMap(unittest.TestCase):
    
        def test_end_to_end(self):
            hash_table = HashTable(10)
    
            print("Test: get on an empty hash table index")
            self.assertRaises(KeyError, hash_table.get, 0)
    
            print("Test: set on an empty hash table index")
            hash_table.set(0, 'first')
            self.assertEqual(hash_table.get(0), 'first')
            hash_table.set(1, 'second')
            self.assertEqual(hash_table.get(1), 'second')
    
            print("Test: set on a non empty hash table index")
            hash_table.set(10, 'third')
            self.assertEqual(hash_table.get(0), 'first')
            self.assertEqual(hash_table.get(10), 'third')
    
            print("Test: set on a key that already exists")
            hash_table.set(10, 'fourth')
            self.assertEqual(hash_table.get(0), 'first')
            self.assertEqual(hash_table.get(10), 'fourth')
    
            print("Test: remove on a key that already exists")
            hash_table.remove(10)
            self.assertEqual(hash_table.get(0), 'first')
            self.assertRaises(KeyError, hash_table.get, 10)
    
            print("Test: remove on a key that doesn't exist")
            self.assertRaises(KeyError, hash_table.remove, -1)
    
            print('Success: test_end_to_end')
    
    
    def main():
        test = TestHashMap()
        test.test_end_to_end()
    
    
    if __name__ == "__main__":
        main()
    

    Github repo

    해피코딩!! 🌟

    좋은 웹페이지 즐겨찾기