그동안 많이 헷갈렸던 용어들에 대해 정리해보았다.

Mutability

Python의 객체와 변수의 관계

• 변수 a에 'Hello'이라는 문자열 객체를 할당할 경우

  • 객체 'Hello'은 특정한 메모리 주소에 할당되고,
  • 변수 a는 이 객체에 바인딩된다.

• 변수 a에 'World'라는 문자열 객체를 재할당할 경우,

  • 객체 'World'는 'Hello'와 다른 메모리 주소에 할당되고,
  • 변수 a는 새로운 객체에 바인딩된다.
  • 객체 'Hello'를 참조하는 변수가 없다면, GC가 이를 메모리에서 제거한다.

• 이에 따라서 아래의 경우, id(a)와 id(b[0])는 같은 값을 갖는다.

a = 'Hello'
b = ['Hello', 'World']

참고 : Immutable과 Mutable

파이썬 자료형의 Mutability

• 파이썬의 자료형은 수정이 가능한 Mutable 객체, 수정이 불가능한 Immutable 객체로 나눌 수 있다.

Mutable 객체 : list, dict, set
Immutable 객체 : int, str, tuple

• dict의 key는 반드시 immutable 객체여야 한다.

• immutable한 tuple은 mutable한 객체를 요소로 가질 수 있다.

  • 또한, tuple의 요소인 mutable 객체는 변경이 가능하다.

test = (1, 2, [3, 4])  # mutable 객체인 list를 요소로 갖는 tuple
test[2][0] = 5
print(test)  # (1, 2, [5, 4])

---

Hashable

Hashing(해싱)

• 우선 Hashing 은 Key Value System을 이용하여 자료를 정리하는 자료구조로, Python의 set, dict가 이에 해당한다.

• 예를 들어, 식당 메뉴를 array에 저장하고, 특정 음식을 찾기 위해서는 linear search(선형검색)을 하면 된다.

  • 배열의 길이가 길어질수록, 처음부터 순차적으로 검색하는 선형검색은 시간이 오래걸린다.

    • 시간복잡도 : O(N)

  • 따라서 이러한 시간적 단점을 해결하기 위해 hash table을 이용한다.

    • 찾고싶은 음식의 이름을 key로 입력하면, hash table은 가격(value)을 제공한다.

    • 시간복잡도 : 일반적으로 O(1) (상수)

      • 요소가 삭제되거나 추가되더라도 걸리는 시간의 변화가 없다.
      • 그 어떤 요소를 검색하더라도, 1개의 단계만 거치기 때문이다.
      • 소요 시간이 array에 비해 훨씬 짧다.

# array
menu = [
    {name : 'coffee', price : 2500},
    {name : 'tea', price : 3000}, 
    {name : 'juice', price : 3500}
]

# hash table
menu {
    coffee : 2500,
    tea : 3000,
    juice : 3500
}

• Hashing은 Hash Function을 이용하여 key를 숫자로 변형하고, 이 숫자를 index로 value를 해시 테이블 내부의 array인 hash table에 저장한다.

• 해시함수

  • 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
  • 1:N 관계를 갖는다.
  • 연산이 빠르고, 충돌이 적고, 고르게 분포될수록 좋은 함수이다.

• 버킷 : 해시 테이블 배열의 각 원소

• 슬롯 : 해시 충돌을 해결하기 위해 하나의 버킷에 여러 개의 데이터를 저장하도록 한 것

• 서로 다른 key에 대해 해시함수가 동일한 숫자를 준 경우를 collision(해시 충돌)이라 하며, 이 경우, 하나의 버킷 내부의 슬롯에 대해 다시 한번 선형 검색을 해야하므로 시간 복잡도가 상수가 아니다.

• 충돌이 슬롯 수보다 많아질 경우 버킷에 더이상 데이터를 저장할 수 없게 되며, 이를 Overflow(오버플로우)라고 부른다.

Hashable

• Hashable object는 해시 함수의 인자가 될 수 있는 객체를 의미한다.

• 즉, 서로 다른 객체는 동일한 hash function을 적용했을 때 서로 다른 숫자가 나와야하며, 이를 토대로 동일한 객체인지, 서로 다른 객체인지 비교할 수 있다.

• 데이터 변경이 가능한 mutable 객체는 데이터를 변경했을 때 해시 함수의 결과값(해시값)이 다르기 때문에 unhashable이다.

• 따라서 hashable한 객체는 immutable해야한다.

• dict의 key는 해시 함수의 인자가 되기 때문에 hashable해야한다.

• set 역시 hash table 구조를 갖고 있기 때문에, set의 원소도 hashable해야 한다.

  • 따라서 리스트는 dict의 key나 set의 원소가 될 수 없다.
  • 일종의 value없이 key만 저장된 hash table이라 생각할 수 있음

immutable하면 항상 hashable한가?

• 답은 NO
• 두 개념이 완전히 같지 않기 때문에, immutable하지만 unhashable인 객체도 있다.
• mutable한 객체를 갖고있는 tuple의 경우, tuple은 immutable이지만 unhashable이다.

Hashable하다면 Immutable하다. ➡️ True
Immutable하다면 Hashable하다. ➡️ False

참고 : Hashable 이란? 쉬운 설명: python
참고 : immutable한 객체는 모두 hashable한가?
참고 : 노마드코더 - 개발자라면 꼭 알아야할 Hash Table 의 모든 것!
참고 : Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편

---

Iterable

• 반복이 가능한 객체를 의미한다.
• list, dict, set, str, tuple 등
• 값을 하나씩 반복해서 꺼낼 수 있다는 뜻으로, 위의 Mutability나 Hashable과는 다른 별개의 개념이다.

map(func, iterable)

• 받은 iterable 객체의 요소에 대해 각각 func을 실행한 결과를 map객체로 반환한다.
• 단순히 map()만 사용하면 map 객체이기 때문에 내부를 확인할 수 없으며, 리스트 등으로 형변환 해주어야 한다.

def negative(x):
    return  -1 * x
    
test_list = [-1, -2, -3]

print(map(negative, test_list))        # <map object at 0x79c2e0e3f7c0>
print(list(map(negative, test_list)))  # [1, 2, 3]

zip(iterable*)

• 동일한 길이를 갖는 iterable 자료형을 묶어 zip 객체로 반환한다.
• 단순히 zip()만 사용하면 zip 객체이기 때문에 내부를 확인할 수 없으며, 리스트 등으로 형변환 해주어야 한다.

print(zip([1, 2], [1, 2]))          # <zip object at 0x79c2e0e4ba40>
print(list(zip([1, 2], [1, 2])))    # [(1, 1), (2, 2)]
print(list(zip([1, 2], [1, 2, 3]))) # [(1, 1), (2, 2)]
# 갯수가 맞지 않으면, 갯수가 적은 부분까지만 zip한다.