나만의 해시함수 만들어보기

나만의 해시 함수를 만들어보자.

1차 시도 (실패)

1. 입력받은 문자열을 ord, 즉 아스키 코드로 변환
2. 변환된 아스키 코드를 2자리씩 나누어 리스트로 저장. ex) [29, 55, 91, 42]
3. 2번에서 실행한 리스트에 인접하는 데이터들을 정수로 더함. ex) [84, 133]
4. 3번에서 실행된 결과를 바탕으로 연산 시작 :
   4-1 : 각 i번째 값을 제곱한 후, 가운데 - 3번 부터 끝까지 폴딩 후 저장
   4-2 : 각 i번째 값을 제곱한 후, 가운데 - 2번 부터 가운데값까지 폴딩 후 저장, 에러가 발생할 경우 무시
   4-3 : 각 i번째 값을 제곱한 후, 4-2번 값으로 나눈 나머지를 저장, 에러가 발생할 경우 무시
   4-4 : 각 i번째 값을 제곱한 후, 이의 첫 글자와 마지막 글자를 더하여 저장
   4-5 : 각 i번째 값을 제곱한 후, 해당 값을 저장
   4-6 : 생성된 값들을 16진수 문자열로 변환하여 반환

코드

def hash(S):
  numbering = ''.join(list(map(str, list(map(ord, S)))))

  length = 1
  numbering = [numbering[0 + i:length + i] for i in range(0, len(numbering), length)]
  result = []
  while len(numbering) >= 2:
    n = numbering.pop()
    m = numbering.pop()
    result.append(int(m + n))

  result2 = []
  for i in range(len(result)):
    k = str(result[i] ** 2)
    p = k[len(k)//2-3:len(k)]
    result2.append(result[i])
    u = str(result[i] ** 2)
    try: result2.append(int(u[len(u)//2-2:len(u)//2]))
    except: pass
    try: result2.append((result[i] ** 2) % int(u[len(u)//2-2:len(u)//2]))
    except: pass
    result2.append(int(u[0] + u[-1]))
    result2.append(result[i] ** 2)
  
  return ''.join(list(map(lambda x : x[2:], list(map(hex, result2)))))

• ...ash 단어를 입력했을 때 해시가 일정하게 생성됨.
• 문자열을 자르고 붙인다고 해도 동일함.
• 문자열을 섞는다 해도 일정한 규칙으로 섞기에 결국엔 해시가 똑같은 곳이 발생함.
• vv, vvvv같이 짝수로 문자열이 같을 경우 동일한 해시를 뱉어냄.

2차 시도 (실패)

순정이 제일 좋은거다... 로직만 생각하면서 짧은 코드로 회귀
i번째 값과 i-1번째 값을 제곱하여 잘라주는 매우 간단한 방법으로 시도

코드

def string_hash(a):
  n = list(map(ord, a))
  r = []
  for i in range(len(n)):
    r.append(str(hex(n[i] ** n[i-1]))[2:18])
  return ''.join(r)
  

• v를 넣었을 때 같은 값이 도출됨.

3차 시도 (실패)

i번째 값과 i-1번째 값을 곱하는 간단한 로직 작성.

코드

def string_hash(a):
  n = list(map(ord, a))
  r = []
  s = 1
  for i in range(len(n)):
    s *= n[i] * n[i-1]
  return s

while True:
  s = input()
  print(string_hash(s))

• hash, shah와 같이 위치만 다른 글자를 넣었을 때 동일한 해시 반환
• ...ash와 같이 동일한 단어를 넣었을 때 뒷자리가 0으로 비슷함

4차 시도 (만족)

비트 시프트 연산자를 써보자고 생각했음.
그리고 DP처럼, 저번에 연산한 값을 기준으로 새로운 연산을 도출하면
차이점이 구분될 것이라고 판단함.

1. 입력받은 문자열을 아스키 코드 리스트로 변환
2. 해시를 생성해주는 고유한 해시값 정의
3. (해시값 << 2) * 해시값 << 4 + 순차적인 아스키코드 <- 해당 식으로 해시값 변수에 다시 대입
4. 이렇게 생성된 해시값을 반으로 잘라 앞과 뒤로 나눈 다음, 앞리스트에서 i번째 값 * 뒷리스트에서 i번째 값으로 곱함
5. 만약 길이가 길면 일정할 수 있도록 최대 32자리로 자름

코드

def string_hash(a):
    n = list(map(ord, a))
    hash_val = 13290570137

    for char in n:
        hash_val = ((hash_val << 2) * hash_val) << 4 + char 
    
    queue = list(str(hash_val))
    forwards = queue[:len(queue)//2]
    backwards = queue[len(queue)//2:]
    queue = []

    for i in range(len(queue)//2-1):
      queue.append(forwards[i] * backwards[i])

    return str(hash_val)[:32]

while True:
    s = input()
    print(string_hash(s))

길이도 동일하게 잘 나오고, 위치만 다른 글자나 똑같은 글자를 여러번 넣었을 때도
고유하게 나온다!!