항해99 TIL 10일차_051822

열공이·2022년 5월 18일
0

TIL

Definitions & Concepts

추상적 자료형(abstract data type, ADT)

  • 컴퓨터 과학에서 자료들과 그 자료들에 대한 연산들을 명기한 것이다.
  • 추상적 자료형은 구현 방법을 명시하고 있지 않다는 점에서 자료 구조와 다르다. 비슷한 개념의 추상적 자료 구조는 각 연산의 시간 복잡도를 명기하고 있지만 추상적 자료형에서는 이것조차 명기하지 않는다.
    In computer science, an abstract data type (ADT) is a mathematical model for data types. An abstract data type is defined by its behavior (semantics) from the point of view of a user, of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This mathematical model contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.
    -- Wikipedia

ADT:
1) implementer가 아닌 유저 입장에서 보는 데이터타입 모델

많은 추상적 자료 구조(그리고 추상적 자료형)의 이름은 구체적 자료 구조의 이름과 동일하다.

  • 스택
  • 연결 리스트
  • 사전

추상 자료형의 예:
잘 알려진 추상 자료형에는 복소수, 리스트, 스택, 큐, 맵, 우선순위 큐, 집합 등이 있다.

https://ontheway.tistory.com/23
https://namu.wiki/w/%EC%B6%94%EC%83%81%EC%A0%81%20%EC%9E%90%EB%A3%8C%ED%98%95

해시테이블

해시테이블/맵은 키를 매핑할 수 있는 구조인 연관 배열 추상 자료형 (ADT)를 구현하는 자료구조이다.

  • 대부분 연산이 (insertion, deletion, search) 시간 복잡도가 O(1)이다 -> 데이터 양과 관련 없이 빠른 성능

해시함수

  • 해시함수란 임의 크기 (random/arbitrary size) 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수이다.
  • key와 value(like dictionary) 테이블을 가질 때 키를 만드는 로직

해싱 (Hashing)

  • 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것
  • 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 기법 중 하나

성능이 좋은 해시 함수의 특징

  • 해시 함수 값 충돌의 최소화
    고윳값 가지는게 쉬울까? -> 생일 문제: 여러 사람이 모여있을 때 생일이 같은 2명이 존재할 확률
  • 쉽고 빠른 연산
  • 해시 테이블 전체에 해시 값이 균일하게 분포
  • 사용할 키의 모든 정보를 이용하여 해싱
  • 해시 테이블 사용 효율이 높을 것

https://gbsb.tistory.com/115?category=655367

해시테이블을 쓸 때 key값의 중복이 일어나는 경우가 흔할 수 있다 -> 상자의 크기를 잘 잡아야한다

로드 팩터 (load factor)

  • 해시 테이블에 저장된 데이터 개수 n을 버킥의 개수 k로 나눈 것
    load factor = n/k
  • 로드 팩터 비율에 따라 해시 함수를 재작성해야 될지 또는 해시 테이블의 크기를 조정해야할지를 결정한다
  • 자바 10에선 디폴드로 lf를 0.75라고 정했음 -> 저장할 공간이 4개 있는데 3개가 차면, 공간 재할당함. 0.75를 넘어설 경우 동적 배열처럼 해시 테이블의 공간을 재할당한다. 파이썬은 0.66, 루비 0.5.
  • 일반적으로 로드 팩터가 증가할 경우 해시 테이블의 성능은 감소하게 된다.

해싱 함수 성능 중요
easy -> modular 연산: 정수형 해싱 기법의 모듈로 연산을 이용한 나숫셈 방식
-> h(x) = x mod m

  • 여기서 h(x)는 입력값 x의 해시 함수를 통해 생성된 결과.
  • m은 해시 테이블의 크기, m은 일반적으로 2의 멱수(거듭제곱수 power/exponent)에 가깝지 않은 소수가 좋다.

충돌 해결 방식
1. 개별 체이닝

  • 해시 테이블 충돌 발생 시 연결 리스트로 쭉쭉 연결하는 방식으로 충돌 없앤다
    1. 키의 해시 값을 계산한다
    1. 해시 값을 이용해 배열의 인덱스를 구한다
    1. 같은 인덱스가 있다면 연결 리스트로 연결한다.
      잘 구현했을 때: 시간 복잡도는 O(1)
      최악의 경우: 모든 해시 충돌이 발생했다하더래도 O(n)의 시간 복잡도가 된다 -> 모든 키가 동일한 해싱 값을 가진 경우, 모든 input이 n개 일 때 n개의 연결 리스트 생김. (그래서 연결 리스트를 쓰니만도 못 하다.)
  1. 오픈 어드레싱
  • 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식
  • probing전략따라 다름. 선형이 제일 쉬움. clustering 문제

문제점:

  • 충돌이 일어나면, 테이블 공간 내 선형탐사 (linear probing)을 통해 빈 공간을 찾아 해결하며, 이 때문에 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다. -> 한 마디: 충돌 일어나면 빈 공간 찾아 붙여주니 모든 원소가 해시값과 일치된 주소에 있지만은 않다.
  • 선형 탐사의 (하나 하나 옮겨다니면서 빈공간 찾는 거) 문제점은 해시 테이블에 저장되는 데이터들이 고르게 분포된지 않고 뭉치는 경향이 있다. --> clustering의 문제는 고유의 값이 적절하게 채워지는 대신 뭉쳐있으니 해시 함수 효율이 떨어지게 됨.
  • 또 오픈 어드레싱 방식은 버킷 사이즈보다 큰 경우에는 삽입할 수 없다. 따라서 일정 이상 채워지면, 더 큰 크기의 또 다른 버킷을 생성한 후 새롭게 복사하는 리해싱 과정이 일어난다.

파이썬은?
해시 테이블로 구현된 파이썬 자료형: 딕셔너리

  • 딕셔너리에 해시테이블(오픈 어드레싱 방식으로 구현)을 사용
  • 체이닝 시 메모리 할당하는 오버헤드가 높아 오픈 어드레싱 채택
    Open addressing is preferred over chaining since the link overhead for chaining would be substantial (100% with typical malloc overhead)
    The initial probe index is computed as hash mod the table size. Subsequent probe indices are computed as explained later.

https://velog.io/@2seunghye/파이썬과-자료구조해쉬-테이블
https://velog.io/@inyong_pang/해쉬-테이블Hash-Table
https://velog.io/@taeha7b/datastructure-hashtable

[자료구조]circular queue, circular deque
https://velog.io/@changyeonyoo/자료구조python-원형큐-덱-CircularQueue-CircularDeque-구현

용어:

배열 복사
얉은 복사와 깊은 복사!

얉은 복사 (shallow copy)

  • 사본을 따로 만들지 않고 원본을 참조하는 방식으로 복사(사실 복사가 아닌 것)
  • Shallow Copy reflects changes made to the new/copied object in the original object.

깊은 복사 (deep copy)

  • Deep copy stores copies of the object's value.

'ShallowCopy' points to the same location in memory as 'Source' does. 'DeepCopy' points to a different location in memory, but the contents are the same.

profile
프로그래머가 되자! 열공!

0개의 댓글