python hash && cache

hash

우리가 흔히 사용하는 캐시는 두가지의 값이 필요합니다. 

 

Key / value , 즉 dictionary의 한 형태를 가지고 있습니다. 그렇다면 key는 어떻게 만들어질까요?

 

아시는 바와 같이 hash값으로 만들어집니다. 즉 특정한 연산을 통해( 특정 모듈러연산) 특정값으로 변환한 값입니다. ( 해시 고유값 분포 및 재연산은 이번 글에서 제외 합니다. )

 

그렇다면 모든값을 hash로 만들수 있을까요? python에서 제공하는 hash 함수를 사용할 수 있을까요?

 

정답은 “NO”입니다. hash()를 사용 할 수 있는 데이터는 immutable 객체만 가능합니다.  즉 mutable은 해시가 불가능 하단 말이 됩니다. 

 

 

immutable / mutable

Immutable과 mutable의 객체는 다음과 같습니다. 

 

python의 문서에서 아래와 같이 확인 가능합니다. 

https://docs.python.org/3/glossary.html#term-hashable

---

An object is hashable if it has a hash value which never changes during its lifetime (it needs a __hash__() method), and can be compared to other objects (it needs an __eq__() method). Hashable objects which compare equal must have the same hash value.

Hashability makes an object usable as a dictionary key and a set member, because these data structures use the hash value internally.

Most of Python’s immutable built-in objects are hashable; mutable containers (such as lists or dictionaries) are not; immutable containers (such as tuples and frozensets) are only hashable if their elements are hashable. Objects which are instances of user-defined classes are hashable by default. They all compare unequal (except with themselves), and their hash value is derived from their id().

---

Immutable과 mutable의 구분 방법은 해당 데이터의 값을 변경한 후 id가 변경되면 immutable , 변경되지 않는다면 mutable 입니다. 

mutable은 처음 메모리를 할당 받은 후 해당 자리에서 메모리를 할당 및 해제 하는 반면, immutable은 고유값이기 때문에 할당 할때마다 메모리 주소가 바뀐다고 생각하시면 됩니다.

# -*- coding: utf-8 -*-
s = 'string'
print(id(s))                  # 4425907088
s += 'id'
print(s)                      # stringid
print(id(s))                  # 4317828656
print(hash(s))                # -6891897941544544670


n = [5, 6]
print(id(n))                  # 140312184155336
n += [10]
print(n)                      # [5, 6, 10]
print(id(n))                  # 140312184155336
print(hash(n))                # TypeError: unhashable type: 'list'

- 참고로 3.3버전 부터 hash의 값이 매변 바뀝니다. 해당 값이 일정하면, injection의 위혐이 있으므로 실행시마다 값이 바뀝니다. 해당 기능은 python 환경변수에서 기존설정으로 변경 가능합니다. (https://docs.python.org/3/using/cmdline.html#envvar-PYTHONHASHSEED 참조)

 

---

Cache for class

 

immutable / mutable를 살펴본 이유는 데이터 캐시를 하기 위해 해시가 사용되기 때문입니다. 캐시는 어떠한 값(파라미터)의 해시값을 저장하고, 새롭게 들어온 값(파라미터)의 해시값를 이미 가지고 있다면 리턴하는 구조입니다.

 

이번 목표는 class의 인스턴스를 캐시하는겁니다. 이 문제를 해결하기 위해 두가지를 해야 하는데 

첫번째는 mutable인 클래스의 변수들을 immutable하게 바꿀것.

두번째는 어떠한 값이 들어와도 캐시 할 수  있는 캐시 패키지 입니다. 

 

 

먼저 첫번째 경우에 class의 변수로 어떤 데이터 타입이 올지 모릅니다. 일반 immutable이 오면 좋지만, mutable이 온다면 hash가 가능하게끔 immutable로 바꿔야 하는 작업이 필요 합니다. 그러기 위해 dictionary와 list를 tuple로 바꿀겁니다. 또한 mutable의 값으로 mutable이 온다면 (ex: 2차원배열, dict 안에 dict 등) 해당 값들도 모두 mutable하게 바꾸기 위해 재귀로 모든 값을 탐색 해야 합니다. 

 

아래는 dict의 모든값을 순회하는 간단한 함수 입니다.  Value 의 타입이 dict일 경우 재귀로 호출하여 동작합니다. 

def dictionary_check(input):
    for key, value in input.items():
        if isinstance(value, dict):
            print(key)
            dictionary_check(value)
        else:
            print(key, value)


dictionary_check({"key": {"value": 10}, "key2": 20, "key3": {"inner_value": 30}})
# key
# value 10
# key2 20
# key3
# inner_value 30

리스트의 경우도 똑같이 구현 가능합니다. 

def list_check(input):
    for value in input:
        if isinstance(value, list):
            list_check(value)
        else:
            print(value)


list_check([1, 2, 3, [4, 5, [6, 7, 8]]])
# 1
# 2
# 3
# 4
# 5
# 6
# 7
# 8

 

위의 두가지를 혼합하면 dict와 list를 겸할수 있게 됩니다. 결과값을 list에 저장 한 후 list를 tuple로 변환하면 hash로 변경이 가능합니다. 

array = []


def dictionary_check(input):
    for key, value in input.items():
        if isinstance(value, dict):
            array.append(key)
            dictionary_check(value)
        elif isinstance(value, list):
            array.append(key)
            list_check(value)
        else:
            array.append(key)
            array.append(value)


def list_check(input):
    for value in input:
        if isinstance(value, list):
            list_check(value)
        elif isinstance(value, dict):
            dictionary_check(value)
        else:
            array.append(value)


list_check([{"key": "value"}, 2, 3, [4, {"key2": [6]}]])
print(tuple(array), hash(tuple))


# list -> tuple : ('key', 'value', 2, 3, 4, 'key2', 6) 
# hash :           274616807

이로서 첫번째에 해당하는 "mutable인 클래스의 변수들을 immutable하게 바꿀것”이 끝났습니다. 

 

두번째는 "어떠한 값이 들어와도 캐시 할 수  있는 캐시 패키지”는 ring를 쓰면 됩니다. 

https://ring-cache.readthedocs.io/en/stable/

서드파티 캐시도 사용 가능하며(redis, memcached 등, 일반 mutable에 대한 캐시도 지원합니다. 앞으로 애용하게될 패키지가 될거 같습니다? ㅎㅎ)

 

 

준비는 끝났습니다. 저는 클래스에  첫번째 소스를 상속하여, hash() 함수를 선언하는 방식으로 만들어 봤습니다. 전체 소스는 아래와 같습니다. 

 

Class cache

# pip install ring
import ring


class ToHash:
    def dictionary_check(self, input, array):
        for key, value in input.items():
            if isinstance(value, dict):
                array.append(key)
                self.dictionary_check(value, array)
            elif isinstance(value, list):
                array.append(key)
                self.list_check(value, array)
            else:
                array.append(key)
                array.append(value)


    def list_check(self, input, array):
        for value in input:
            if isinstance(value, list):
                self.list_check(value, array)
            elif isinstance(value, dict):
                self.dictionary_check(value, array)
            else:
                array.append(value)


    def __hash__(self):
        array = []
        self.dictionary_check(self.__dict__, array)
        return hash(tuple(array))




class Test(ToHash):
    def __init__(self, v, s="str", d={}):
        self.v = v
        self.s = s
        self.d = d


    def __repr__(self):
        return "Test {}".format(self.v)


    def __str__(self):
        return "Test {}".format(self.v)


@ring.lru()
def cache_test(obj):
    print(“cache_test ->", obj, obj.v, obj.s, obj.d)
    return obj




if __name__ == '__main__':
    t1 = Test(10, "123", {"key": [10, 20, 30]})
    t2 = Test(10, "123", {"key": [10, 20, 30]})
    t3 = Test(10, "123", {"key": [10, 20, 40]})
    t4 = Test(10, "123", {"key": [10, 20, 40]})


    print("result", cache_test(t1))
    print("result", cache_test(t2))
    print("result", cache_test(t3))
    print("result", cache_test(t4))


# 결과값 
# cache_test -> Test 10 10 123 {'key': [10, 20, 30]}
# result Test 10
# result Test 10
# cache_test -> Test 10 10 123 {'key': [10, 20, 40]}
# result Test 10
# result Test 10

Class를 해시 하기 위한 소스 입니다. 

 

대상 클래스는 Test()로 cache_test() 함수에 파라미터로  인스턴스를 넣습니다. 이 해당 인스턴스를 캐시하여 리턴값을 가지고 있는게 목표 입니다. 

 

캐시는 @ring.lru() 를 통해 데코레이터에서 모든걸 처리 합니다. 

그리고 @ring.lru()에서 해당 객체의 hash()를 호출하기 때문에 해당 class의 hash()를 선언하였으며, 해당 함수에서는 클래스 내 변수를 tuple로 변환후 hash값을 반환하는 형식으로 되어 있습니다. 

 

결과값을 보는 바와 같이 t1, t2 그리고 값이 다른 t3, t4에 cache_test()함수 안의 print문이 한번씩 동작하는것을 확인 할수 있습니다. 

결국 데이터값이 다르기 때문에 해쉬가 달라지며, 캐시가 정상작동하는것을 확인 할 수 있습니다. 

 

이상 끝!

 

 

- 해당 소스는 dict / list만 고려했을뿐 , set과 기타 다른 클래스는 고려 하지 않았습니다. 적절히 수정해서 사용하시면 됩니다. 

- 처음 frozenset으로 방향을 잡았다가, dict의 키값만 set으로 변경되는것을 확인후 급 선회하엿습니다. , 또한 frozenset으로 변경하면 해당 데이터에 set에 대한 메소드를 사용할수 없기 때문도 있었습니다. 

 

 

 

 

 

- 참고 자료 

https://medium.com/@meghamohan/mutable-and-immutable-side-of-python-c2145cf72747

https://medium.com/@mitali.s.auger/python3-sometimes-immutable-is-mutable-and-everything-is-an-object-22cd8012cabc