Data Structure and Algorithms (3)
1. 연결 리스트 (Linked List)
- 구조: 데이터 + 다음 데이터를 가리키는 주소
- 장점: 미리 데이터 공간을 할당할 필요가 없다.
- 단점
1) 별도의 데이터 공간 필요 (주소값 할당을 위한) -> 저장 공간의 효율이 떨어짐
2) 연결 정보를 찾는 시간이 필요해 접근 속도가 느림.
3) 중간 데이터 삭제시 앞 뒤 데이터 연결을 위한 부가작업 필요
코드
class Node: def __init__(self, data, next = None): self.data = data self.next = next ㅤ class NodeMgmt: def __init__(self, data): self.head = Node(data) ㅤ def add(self, data): if self.head == '': self.head = Node(data) else: node = self.head while node.next: node = node.next node.next = Node(data) ㅤ def desc(self): node = self.head while node: print(node.data) node = node.next ㅤ def delete(self,data): if self.head == '': print('empty') return elif self.head.data == data: temp = self.head self.head = self.head.next del temp return else: node = self.head while node.next: if node.next.data == data: temp = node.next node.next = node.next.next del temp return else: node = node.next ㅤ def search(self,data): node = self.head while node: if node.data == data: return node else: node = node.next print('찾는 데이터 없음') ㅤ ㅤ link = NodeMgmt(0) ㅤ for data in range(1,10): link.add(data) ㅤㅤ link.delete(0) link.delete(5) ㅤ link.desc()코드2 (double linked list)
class Node: def __init__(self, data, next = None): self.data = data self.next = next ㅤ class NodeMgmt: def __init__(self, data): self.head = Node(data) ㅤ def add(self, data): if self.head == '': self.head = Node(data) else: node = self.head while node.next: node = node.next node.next = Node(data) ㅤ def desc(self): node = self.head while node: print(node.data) node = node.next ㅤ def delete(self,data): if self.head == '': print('empty') return elif self.head.data == data: temp = self.head self.head = self.head.next del temp return else: node = self.head while node.next: if node.next.data == data: temp = node.next node.next = node.next.next del temp return else: node = node.next ㅤ def search(self,data): node = self.head while node: if node.data == data: return node else: node = node.next print('찾는 데이터 없음') ㅤ ㅤ link = NodeMgmt(0) ㅤ for data in range(1,10): link.add(data) ㅤ link.delete(0) link.delete(5) ㅤ link.desc()
2. 해쉬 테이블 (Hash Table)
-
구조: key에 value를 저장
-
용어
해쉬(hash): 임의 값을 고정 길이로 변환하는 것
해쉬 테이블 (hash table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
해슁 함수 (hashing function): 키에 대해 산술 연산 이용해 데이터 위치를 찾을 수 있는 함수 (or 저장할 때 변환)
해쉬 값 or 해쉬 주소 (hash address): 키를 해슁 함수로 연산해서 해쉬 값을 알아내고 이를 기반으로 해쉬테이블에서 해당 키에 대한 데이터 위치를 일관성있게 찾을 수 있음
슬롯 (slot): 한 개의 데이터를 저장할 수 있는 공간
*저장할 데이터에 대해 키를 추출할 수 있는 별도 함수 존재 O -
장점
1) 데이터 저장 및 읽는 속도가 빠르다.
2) 키에 대한 데이터의 중복처리가 쉽다. -
단점
1) 저장공간이 많이 필요하다
2) 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도의 자료구조가 필요하다. -
주요용도
1) 검색이 많이 필요한 경우
2) 저장 삭제 읽기가 빈번한 경우
3) 캐쉬 구현 (중복 확인이 쉽기 때문에)
코드1
hash_table = list(i for i in range(10)) ㅤ def hash_func(key): return key % 5 ㅤ def storage_data(data,value): key = ord(data[0]) hash_address = hash_func(key) hash_table[hash_address] = value ㅤ def get_data(data): key = ord(data[0]) hash_address = hash_func(key) return hash_table[hash_address] ㅤ ##ord(): 문자의 ASCII코드 리턴: 영어 숫자만 ##unicode: 모든 언어를 코드 리턴 ㅤ storage_data('Andy', '01011111111') storage_data('Dave', '01022222222') storage_data('Trump', '01033333333') ㅤ print(get_data('Andy'))코드2
hash_table = list(i for i in range(10)) ㅤ def get_key(data): return hash(data) ㅤ def hash_func(key): return key % 8 ㅤ def save_data(data,value): hash_address = hash_func(get_key(data)) hash_table[hash_address] = value ㅤ def read_data(data): hash_address = hash_func(get_key(data)) return hash_table[hash_address] ㅤ save_data('Dave', '1') read_data('Dave')충돌방지1) chaining
hash_table = list(0 for i in range(8)) ㅤ def get_key(data): return hash(data) ㅤ def hash_func(key): return key % 8 ㅤ def save_data(data,value): index_key = get_key(data) #링크드 리스트 내 같은 해쉬값가진 데이터의 구분을 키값으로 함 hash_address = hash_func(index_key) if hash_table[hash_address] != 0: #데이터가 들어있다면 for index in range(len(hash_table[hash_address])): #해당 해쉬테이블 리스트의 길이만큼 반복하면서 리스트 속 리스트이 요소 하나하나 반복해줌 if hash_table[hash_address][index][0] == index_key: hash_table[hash_address][index][1] = value return #만약 [0] (=인덱스) 이 같다면 똑 같은 값이라는 소리기 떄문에 값을 수정해주고 return hash_table[hash_address].append([index_key, value]) #for 문이 끝났다는 말은 새로운 데이터라는 뜻이기 때문에 추가해줌 else: hash_table[hash_address] = [[index_key, value]] ㅤ def read_data(data): index_key = get_key(data) hash_address = hash_func(index_key) if hash_table[hash_address] != 0: for index in range(len(hash_table[hash_address])): if hash_table[hash_address][index][0] == index_key: return hash_table[hash_address][index][1] return None else: return None ㅤ save_data('Dave', '111') save_data('James', '222') save_data('Dd', '333') ㅤ print(hash_table) print(read_data('James'))충돌방지2) linear probing
hash_table = list(0 for i in range(8)) ㅤ def get_key(data): return hash(data) ㅤ def hash_func(key): return key % 8 ㅤ def save_data(data,value): index_key = get_key(data) #링크드 리스트 내 같은 해쉬값가진 데이터의 구분을 키값으로 함 hash_address = hash_func(index_key) if hash_table[hash_address] != 0: #데이터가 들어있다면 for index in range(hash_address, len(hash_table)): if hash_table[index] ==0: hash_table[index] = [index_key, value] return elif hash_table[index][0] == index_key: #데이터 주소의 키가 동일하다면 값 업데이트 hash_table[index][1] = value return else: hash_table[hash_address] = [index_key, value] ㅤ def read_data(data): index_key = get_key(data) hash_address = hash_func(index_key) if hash_table[hash_address] != 0: #데이터가 들어있다면 for index in range(hash_address, len(hash_table)): if hash_table[index] == 0: #빈공간이 있다는 것 = 데이터가 저장된적이 없음 return None elif hash_table[index][0] == index_key: return hash_table[index][1] else: return None ㅤ save_data('Dave', '111') save_data('James', '222') save_data('Dd', '333') ㅤ print(hash_table) print(read_data('James'))충돌방지3) 공간 확보 (hashlib 사용)
import hashlib ㅤ data = 'test'.encode() #byte로 바꿈 hash_object = hashlib.sha1() hash_object.update(b'test') hex_dig = hash_object.hexdigest() print(hex_dig)
본 게시글은 fastcampus 이준희강사 수업을 듣고 개인적으로 정리한 내용임을 밝힘.
Back-end-dev