Set
- 데이터를 비순차적(unordered)으로 저장할 수 있는 순열 자료구조(collection)이다.
- 삽입 순서대로 저장되지 않는다. 즉, 특정한 순서를 기대할 수 없다.
- 수정 가능하다(mutable).
- 동일한 값을 여러번 삽입 불가능하다. 만약 동일한 값이 여러번 삽입되면 하나의 값만 저장된다.
- Fast Lookup이 필요할때 주로 쓰인다.
Set의 구조
Array와 달리 요소들을 순차적으로 저장하지 않는다.
- Set에서 요소들이 저장될 때의 순서
- 저장할 요소의 값의 hash를 구한다.
- 해쉬값에 해당하는 공간(bucket)에 값을 저장한다.
이렇게 set은 저장하고자 하는 값의 hash값에 해당하는 bucket에 값을 저장하므로 순서가 없다. 순서가 없기 때문에 indexing도 없다.
해쉬값을 기반으로 저장하기 때문에 look up(특정 값을 포함하고 있는지 확인하는 것)이 굉장히 빠르다. Set의 총 길이와 상곤 없이 단순히 해쉬값 계산 후 해당 bucket을 확인하면 되기 때문에 O(1)이다.
hash는 단방향 (one way) 암호화 입니다. 단방향이란 한번 암호화 하면 복호화가 안된다는 뜻입니다. 실제 값의 길이와 상관없이 hash 값을 일정한 길이를 가집니다. 그럼으로 Hash는 주로 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑할때 사용된다.
When To Use Set
- 중복된 값을 골라내야할때
- 빠르 Look Up을 해야할때
- 위의 상황들에서 순서가 상관이 없을때
Diactionary
다른 언어에서는 hashmap 또는 hash table이라고 하기도하는 dictionary는 Key-value의 값을 저장할 수 있는 자료구조이다. 실제 데이터 값과 데이터를 설명하는 Key의 대응관계를 표현할 때 유용하다.
특성
- 특성 순서대로 데이터를 리턴하지 않는다.
- Key의 값은 중복될 수 없다. 만약 중복된 key가 있다면 먼저 있던 key와 value를 대체한다.
- 수정 가능하다(mutable).
Dictionary 내부구조
- Set과 비슷하게 Key의 해쉬값을 구한 후 해쉬값에 속해있는 bucket에 값을 저장한다.
- set과 마찬가지로 순서가 없고 중복된 key값은 허용되지 않는다.
When To Use Dictionary
- 키와 값을 묶어서 데이터를 표현해야할 때
- 데이터베이스에서 읽어들인 값을 dictionary로 변환해서 자주 사용한다.
Dictionary 실습
# dictionary create 1
dictionary1 = {'name':['Ryan','Lee'], 'job':'sw engineer', 'address': {'city':'seoul', 'zip_code':'1234'} }
# dictionary create 2
dictionary2 = {}
dictionary2['name'] = ['Ryan', 'Lee']
dictionary2['job'] = 'sw engineer'
dictionary2['address'] = {'city':'seoul', 'zip_code':'1234'}
# dictionary create 3
dictionary3 = dict(name=['Ryan','Lee'], job='sw engineer', address={'city':'seoul','zip_code':'1234'})
# dictionary create 4
dictionary4 = dict([('name',['Ryan','Lee']), ('job','sw enginner'), ('address',{'city':'seoul','zip_code':'1234'})])- 첫번째 방법은 데이터가 주어지거나 딕셔너리의 내용이 고정되어 있는 경우 사용되는 방법이다.
- 두번째 방법은 dictionary2변수를 선언해놓고 데이터 베이스를 조회해서 필요한 정보를 동적으로 채워야 할때 편리하다.
- 세번째 방법은 숫자로 딕셔너리의 키로 사용할 수 있지만 문자열만 키로 사용되는 경우 사용할 수 있는 방법이다.
- 네번째 방법은 튜플로 받아온 정보로 키와 값을 만들어야 할 경우에 사용할 수 있다.
Hash 실습
SHA 함수를 이용하여 문자열 데이터를 입력받아서 해시값을 구할 수 있다.
import hashlib
def sha1_hash(input_str):
hash_obj = hashlib.sha1(input_str.encode())
hash_value = hash_obj.hexdigest()
return hash_value
wecode_hash_value = sha1_hash('wecode')
print(wecode_hash_value)
print(len(wecode_hash_value))
hash_value_1234 = sha1_hash('1234')
print(hash_value_1234)
print(len(hash_value_1234))이처럼 hash 값은 일정한 길이를 가지고, 주로 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑할때 사용된다.
해시함수는 같은 문자열에 대해서는 같은 인덱스를 구할 수 있어야 해시함수로 구한 버킷의 인덱스를 저장 후에도 구할 수 있습니다.
해시테이블은 해시함수와 버킷(bucket)의 리스트로 구현할 수 있는데 위의 wecode 의 해시값인 '283463014a3f8ab829fcf9087ff85d50da1d1bb6' 와 '1234'의 해시값인 '7110eda4d09e062aa5e4a390b0a572ac0d2c0220'을 버킷의 주소인 인덱스를 구할 때 사용하기에는 무리가 있어 보입니다.
버킷의 크기에 따른 인덱스로 변환하는 방법은 입력된 문자열의 각자리의 숫자를 더하는 방식인 Digit folding 과 비트연산을 활용한 방법등 다양한 방법이 있지만 우리는 이미 SHA1 알고리즘으로 해시값을 구하였으므로 간단하게 버킷의 사이즈로 나누는 방법인 나눗셈법을 적용하면 버킷의 인덱스를 초과하지 않는 인덱스를 구할 수 있습니다.
➡ Hash Table Repl.it 문제 풀이
