Hash
- 어떤 크기가 정해진 키를(데이터) 고정된 크기의 값(value)로 변화시켜서 저장하는 것
- 키에 대한 hash 값을 사용해서 값 저장하고 key value 갯수에 따라서 동적으로 크기가 증가하는 associate array
- hash value를 구하는 과정을 hasing이라함. 이 Algorithm을 hash function이라고 함.
- hash value 자체를 index로 사용해서 average time complexity가 O(1)로 굉장히 빠름
Hash function
- 원래 값이나 키를 색인하는데 사용되고, 그 값이 관련된 데이터가 검색될 때마다 사용된다.
- 데이터의 효율적 관리를 목적. 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 함수.
- 계산이 단순하고 중복없이 해시값을 만들어 줄 수 있는 함수가 좋음(충돌이 일어나지 않을 수록 좋다.)
- string을 받고 숫자를 반환하는 함수 (string에 대해 숫자를 mapping으로 할당)
Hashing
- key 값에 직접 산술적인 연산 적용하고 항목이 저장되어 있는 테이블의 주소 계산해서 항목에 접근
- mapping하는 과정 말한다.
- hash table을 이용해서 searching
hashing procedure
Hash table
해쉬함수를 사용하여 해시값으로 매핑하고 해시값을 색인(index) 또는 주소 삼아서 값(value)을 키와 함께 저장하는 자료구조
장점
- 해시 충돌(hash collision) 발생 가능성이 있긴 하지만, 데이터를 적은 자원으로 관리할 수 있어서 유용하다.
- 클라우드, 하드디크스에 존재하는 데이터(key)들은 무한에 가깝고 이것들은 몇 개의 해쉬값으로 매핑하면서 작은 크기의 캐시메모리로도 프로세스를 관리 할 수 있다.
- index에 hash value를 사용하므로 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행가능
- index은 간단한 함수로 작동하므로 매우 효율적
- 항상 동일한 hash value를 return하고 해당 색인만 알면 hash table의 크기에 상관없이 데이터에 빠르게 접근 가능
- Data access시(Deletion, Insertion, Searching)시 time complexity는 O(1)을 지향함.
인프런
s = bacaAacba
t = abc
abc의 구성이 bacaAacba안에서 존재할까 라는 문제이다.
lt rt가 순차적으로 진행되면서 SH(해쉬테이블)에 요소개수를 적고
tH(해쉬테이블)에 a b c 각 요소가 1개씩 들어있으니까 sH 해쉬테이블과 비교하면서 요소종류와 개수가 같으면 카운트 해준다.
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function compareMaps(map1, map2) {
// 아나그램이면 키의 사이즈가 같아야 한다.
if (map1.size !== map2.size) return false;
for (let [key, val] of map1) {
// map2에는 없다면
// key의 벨류값이 다르면
// key값의 벨류값이 몇인가 가져오는 것
if (!map2.has(key) || map2.get(key) !== val) return false;
}
return true;
}function solution(s, t) {
let answer = 0;
// 두 개를 만든다.
let tH = new Map();
let sH = new Map();
// x라는게 있으면 x값에다가 + 1해서 카운팅해라
for (let x of t) {
if (tH.has(x)) tH.set(x, tH.get(x) + 1);
else tH.set(x, 1);
}// t개수 하나 적게 돌면서 세팅
let len = t.length - 1;
for (let i = 0; i < len; i++) {
if (sH.has(s[i])) sH.set(s[i], sH.get(s[i]) + 1);
else sH.set(s[i], 1);
}// lt를 0으로 해주고 for문이 투포인터하면서 슬라이딩 윈도우까지 밀고 가는 것
// 슬라이딩 윈도우는 rt끝나면 끝난다.
let lt = 0;
for (let rt = len; rt < s.length; rt++) {
if (sH.has(s[rt])) sH.set(s[rt], sH.get(s[rt]) + 1);
else sH.set(s[rt], 1);
if (compareMaps(sH, tH)) answer++;
// 빼고 추가 비교(if lt => if rt => copareMaps)
sH.set(s[lt], sH.get(s[lt]) - 1)
if (sH.get(s[lt]) === 0) sH.delete(s[lt]);
lt++;
}
return answer;
}
let a = "bacaAacba";
let b = "abc";
console.log(solution(a, b));
</script>
</body>
</html>
<출처 : 자바스크립트 알고리즘 문제풀이(코딩테스트 대비): 김태원>
참고:
자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의
자바스크립트(JavaScript)로 코딩테스트를 준비하시는 분을 위한 강좌입니다. 재미있게 풀 수 있는 기초 단계 문제부터 고급 알고리즘까지 단계별로 차근차근 배우도록 설계된 강좌입니다., 개발
www.inflearn.com
해시 알고리즘 (hash algorithm)
오늘은 해시에 대해서 알아보도록 하겠습니다. Hash 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것 키에 대한 해시 값을 사용하여 값을 저장하고 키-값 쌍
coding-sojin2.tistory.com
https://jahyun-dev.github.io/posts/cryptocurrency-1/
암호화폐 스터디 1 : Hash Function - DEV LOG
jahyun-dev.github.io
https://power-overwhelming.tistory.com/42
[자료구조/알고리즘] 해시(Hash) 란?
Hash 개념 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 a
power-overwhelming.tistory.com
'JavaScript > JS_Algorithm' 카테고리의 다른 글
| [인프런 - JS 알고리즘 문제풀이] stack판단3 (0) | 2021.08.05 |
|---|---|
| [인프런 - JS 알고리즘 문제풀이] stack판단2 (0) | 2021.08.05 |
| [인프런 - JS 알고리즘 문제풀이] stack판단 (0) | 2021.08.05 |
| [인프런 - JS 알고리즘 문제풀이] 공통인자 구해보기 (0) | 2021.08.05 |
| [인프런 - JS 알고리즘 문제풀이] Array 문제 (0) | 2021.08.05 |