나를 잃지 말자

수명 주기 동안 결코 변하지 않는 해시값을 갖고 있고(__hash__() 메서드가 필요) 다른 객체와 비교할 수 있으면(__eq__() 메서드가 필요), 객체를 해시가능하다고 한다. 동일(==)하다고 판단되는 객체는 반드시 해시값이 동일해야 한다.

• 모든 불변형은 해시가능하다.
  • 조금 틀린 말이다. tuple의 경우 불변형이지만, 해시불가능한 객체를 참조할 때는 튜플 그 자체도 해시불가능해진다.
• 사용자 정의 자료형은 기본적으로 해시가능하다. 그 이유는 __hash__() 가 id() 를 이용하여 구하므로 모든 객체가 서로 다르기 때문
• 파이썬 dictionary의 경우 hashtable, open addressing 방식으로 구현되어 있다. dict.get("key")로 조회를 하는 경우 다음 순서를 따른다.
  • "key"의 hash값으로 먼저 조회
  • hash값이 hashtable에 존재하더라도 그 hash값을 가지는 원소의 "key"를 비교한다. hash와 key값 비교(==)가 완료된 것의 value를 반환한다.
• 따라서 아래의 예제가 이해된다.즉, key는 가변적이고 hash값은 dictionary 객체가 생성될 때의 값을 사용한다는 것을 알기.

• class MyList(list):
      # 임의로 수명주기 동안 변하지 않는 hash가 아니라
      # 수명주기 동안에도 변하는 hash를 준 예제
      def __hash__(self):
          return sum(self)
  
  
  my_list = MyList([1, 2, 3])
  
  my_dict = {my_list: 'a'}
  
  print(my_dict.get(my_list))  # a
  
  my_list[2] = 4  # __hash__() becomes 7
  print(next(iter(my_dict)))  # [1, 2, 4], 즉 key가 변경
  
  print(my_dict.get(MyList([1, 2, 3])))  
  # None, hash값은 같지만 key비교가 안맞아서 조회 불가 
  
  print(my_dict.get(MyList([1, 2, 4])))  
  # None, dictionary 객체가 생성될 때의 hash값(6)과 안맞아서 조회 불가
  # 이 부분이 중요, 같은 key값을 넣었지만, dictionary(hashtable)이 보유한 hash는 6이라서 안된 점
  # 즉, line:14에서 key변경을 해도 dictionary는 보유한 hash를 업데이트 하지 않음(6으로 고정)
  
  my_list[0] = 0  # __hash_() is 6 again, but for different elements
  print(next(iter(my_dict)))  # [0, 2, 4], 즉 key가 변경
  
  print(my_dict.get(my_list))  
  # 'a', hash값비교(6==6), key값비교(MyList([0,2,4])==MyList([0,2,4]))돼서 조회가능

  • 따라서,
    • hash메소드는 객체 수명 주기 동안 불변한 값으로 정의하라는 지침이 있는 이유를 알 수 있다.
    • dictionary key는 왜 hashable만 받게 해둔 것인지를 알 수 있다.

set/dictionary는

hash table

hash collision을 막는 방법으로는 closed hashing(open addressing, 같은 의미인데 하나는 closed, 하나는 open...)

따라서, 특정 element가 set/dictionary에 존재하냐는

element의 hash값을 구하고 그 위치만 따지면 되므로 O(1)

참고자료:

stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented

jinyes-tistory.tistory.com/10

jinyes-tistory.tistory.com/11

jinyes-tistory.tistory.com/12