블록체인이란
관리대상의 데이터(ex. 거래내역 등)를 '블록'이라고 하는 소규모 데이터들이
(P2P 방식을 기반으로 생성된) 체인 형태의 연결고리같은 분산 데이터 저장환경에 저장되어
누구든 임의로 수정할 수 없고, 누구든 변경의 결과를 열람할 수 있는 데이터 위변조 방지 기술이다.
쉽게 말해 위조 불가능한 공공 거래 장부이고 많은 사람들의 희노애락을 결정지었던 '비트코인'이 대표적인 예이다.

블록체인의 데이터위변조의 핵심이 되는 기술이 바로 해시(hash)이다.

위키백과를 참고해보면
해시 함수란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말한다.
해시 테이블이라는 자료구조에 사용되며,
데이터의 효율적인 관리와 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 널리 사용된다.

해시 테이블 : 데이터의 해시 값을 테이블 내의 주소로 이용하는 알고리즘. 출처
데이터가 들어갈 테이블을 크게 확보한 후 입력받은 데이터를 해시를 통해 나온 주소에 담는 것.

즉, hash function : key(임의길이의 정보) -->(hashing)--> hash value(고정길이의 암호문 즉, 해쉬값)으로 보면 된다.
EX) 14031781389321768(원본데이터) -> hash function -> 4291(테이블 내의 주소값)

입력 받은 데이터를 완전 새로운 모습의 데이터로 만들기 때문에 해시 후 데이터로는 전 데이터를 알아 볼 수 없는
이 특성이 암호화영역에서 사용 되는 것이다.

또한 길이가 제각각인 데이터를 일정한 길이의 데이터로 출력하는 데이터 축약이 가능하기 때문에
기존의 선형자료구조에서 탐색이나 삽입에 시간이 걸리는 것에 비해
해시 전후 대비하여 엄청난 효율을 기대할 수 있다.

키의 개수 = 해시테이블의 크기

전체 키의 개수인 U만큼 해시테이블 T를 생성하고 실제 사용하는 key k만큼 저장하는 방식이다.
전체 키의 개수 U와 실제 사용하는 키의 개수 k의 차이로 알 수 있는 부분은 적재율과 효율성이다.
적재율이란 현재 저장된 키의 개수를 전체 테이블의 개수로 나눈 값인데
현재 저장된 데이터가 많아질 수록 충돌확률이 높아지고, 연결 리스트 탐색 확률도 증가한다.
때문에 실제 사용하는 k가 키의 개수인 U와 차이가 많이 나는 경우에는 효율성이 떨어질 수 있다.
.
중복이 없다는 전제하에 해시테이블의 한 버킷에 매핑되는 키의 개수 평균은 1 이하이고, 이상일 경우 해시 충돌을 일으킨다.

여기서 해시충돌이 일어나는 경우 사슬처럼 고리에 고리를 엮는다는 의미의 체이닝 기법을 사용하게 되는데,
키에 매칭된 해시값에 이미 다른 키값이 들어있는 경우 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결할 수 있다.
심한 경우 복잡도의 증가라는 문제를 불러 올 수 있지만
데이터의 key값만 알면 즉시 위치를 찾는 것이 가능하므로 매우 빠른 속도로 처리가 가능하다.

대부분의 경우가 많은 key값을 상대적으로 적은 hash value값으로 변환하기 때문에 해시충돌이 일어난다.
해시충돌이란 해시함수가 서로 다른 두 개의 키에 동일한 해시값을 내는 것이다.

대부분의 해시함수는 해시충돌을 일으키고 이를 완전히 방지한다는 것은 어렵기 때문에
충돌을 허용하되 최소화 하는 방법을 사용한다.

충돌을 최소하 하는 방법 중 하나는 충돌이 적은 해시함수를 만드는 것이다.
그런 해시함수 simple uniform hash함수를 만드는 조건은

계산된 해쉬값들이 동일한 확률로 골고루 나타날 것 각각의 값들은 서로 연관성 없이 독립적으로 생성될 것

해시충돌을 방지하는 방법은 크게 두가지이다.
해시테이블 외부에 새 공간을 할당하는 Open Hasing, 처음 주어진 해시테이블 공간 안에서 해결하는 closed Hashing이다.
Open hashing : Chaining(Open&closed hashing) - 삽입연산, 삭제연산, 탐색연산
Closed hashig : Open adressing - Linear Probing(선형탐색), Quadratic Probing(제곱탐색), Double Hashing, Rehashing