해시 충돌시에 검색할 때

코딩 채널

알림 알림 중 알림 취소

구독자 4409명 알림수신 85명 @은월영

프로그래밍 및 코딩 채널

질문 해시 충돌시에 검색할 때

aa (211.234)

추천 0 비추천 0 댓글 40 조회수 211 작성일 2023-01-07 07:58:35

⚠️ 이 게시물은 작성자가 삭제할 수 없도록 설정되어 있습니다.

https://arca.live/b/programmer/66981853

해시 충돌시에 저장하는 체이닝 방법이나 개방주소법은 이해는 했는데
저장 후에 검색할때는 충돌나서 다른곳에 저장했는지 어떻게 알아?
충돌나는거 두개 어짜피 해시함수 거치면 동일 결과값 나오는데, 해당 주소값에 있는 결과가 어떤거의 Value인지 모르지않아?

댓글 [40] 글쓰기

nano

2023-01-07 08:40:43 답글

원래 key로 찾아야지

펼쳐보기▼

aa (211.234)

2023-01-07 08:42:03 삭제 수정 답글

키값이 해시함수 거쳤을때 동일해서 충돌난건데 어떻게찾아?

펼쳐보기▼

aa (211.234)

2023-01-07 08:42:39 삭제 수정 답글

해시함수 말고 다른방법으로 찾아야한다는거야?

펼쳐보기▼

nano

2023-01-07 08:45:03 답글

평문으로 찾아야지

펼쳐보기▼

aa (211.234)

2023-01-07 08:51:05 삭제 수정 답글

충돌난 두 평문을 키값으로 변환하면 결국 동일할텐데 어떻게 구분하는지 모르겠어...

펼쳐보기▼

aa (211.234)

2023-01-07 08:51:19 삭제 답글

nano

2023-01-07 08:54:16 답글

평문 --(해시함수)--> 해시값

펼쳐보기▼

nano

2023-01-07 08:59:09 답글

설마 평문 같은거 두개 넣는걸 말하는거임? 그거는 당연히 구분을 못하지

펼쳐보기▼

nano

2023-01-07 08:59:37 답글

그거를 구분하는 방법은 세상 어디에도 없음

펼쳐보기▼

aa (211.234)

2023-01-07 09:02:59 삭제 수정 답글

아니아니 다른단어가 충돌났을때 구분하는방법 말하는거야

펼쳐보기▼

aa (211.234)

2023-01-07 09:03:30 삭제 수정 답글

내가 뭔가 잘못이해했나봐... 더 찾아보고 올게

펼쳐보기▼

nano

2023-01-07 09:23:25 답글

"hi" -> 3
"hello" -> 3
이렇게 충돌나는데 "hi"를 찾고싶으면 해시테이블에서 인덱스 3인거 쭉 보면서 "hi"를 찾으면 되잖아

펼쳐보기▼

aa (211.234)

2023-01-07 09:47:46 삭제 수정 답글

테이블에 인덱스와 벨류말고 다른게 저장이 안되지않아? 평문으로 비교가 안되는줄 알아서 물어봤어

펼쳐보기▼

nano

2023-01-07 09:48:20 답글

저장을 하면 되지요 안되는게 어딨노

펼쳐보기▼

호두와몬드

2023-01-07 09:36:02 답글

해시값으로 테이블 상의 인덱스는 빠르게 찾았으니까
그 이후에는 평문으로 비교해야 함
충돌이 많으면 당연히 해시 테이블 쓰는 의미가 없어짐

펼쳐보기▼

ㅇㅇ

2023-01-07 09:41:44 답글

*수정됨

무슨소린지 모르겠는데 해시가 충돌한다는건 아마 뭔가 잘못된 값을 넣었을거임. 평문이 다른 두 해시값 자체가 충돌할 가능성은 극히 낮다.

펼쳐보기▼

호두와몬드

2023-01-07 09:46:12 답글

이건 해시 알고리즘을 뭘 쓰고, 테이블 크기가 어떻게 되느냐에 따라 다를 수 있음..

펼쳐보기▼

ㅇㅇ

2023-01-07 09:47:11 답글

일반적인 이야기를 한거임. 특수한 경우가 아니라

펼쳐보기▼

호두와몬드

2023-01-07 09:50:15 답글

이 사람은 직접 구현해보면서 그 충돌에 대한 처리를 어떻게 할지 고민하는 것 같은데 그럴 일 없다는 답변은 필요가 없지

펼쳐보기▼

nano

2023-01-07 09:53:25 답글

충돌이 나는게 더 일반적인 상황 아님? 해시값 자체가 같을 확률은 낮아도 테이블 만들때는 모듈로 하지않나

펼쳐보기▼

호두와몬드

2023-01-07 09:58:18 답글

음.. 보통 좋은 해시 알고리즘이라고 하면 충돌이 없이 분산이 잘 되는 쪽을 얘기하니까
충돌이 매번 나는 건 당연히 일반적인게 아니고
충돌이 있을 수 있다 = 충돌이 거의 없다는 의미에서 일반적이라고 말한 거 아닌가?

펼쳐보기▼

nano

2023-01-07 10:03:32 답글

내생각에 그거는 해시값을 쓰는 용도에 따라 달라질거 같은데

해시를 비가역적 데이터 암호화 용도로 쓴다(비밀번호 저장 등)->해시값 자체를 저장하기 때문에 충돌이 거의 안난다고 봐도 무방
해시값을 해시테이블의 인덱스로 쓴다->해시값으로 가능한 값의 종류만큼의 테이블을 만들 수 없으니 modulo를 하든 뭘 하든 범위 제약을 줘야함->충돌이 불가피하고 충돌시 해결하는 방법이 필요함

이렇게 이해했음

펼쳐보기▼

호두와몬드

2023-01-07 10:06:30 답글

*수정됨

여기서는 테이블 얘기고..
충돌이 아예 없다는 것은 아니고 없을수록 좋은 거긴 하니까
충돌 가능성이 낮은 쪽이 일반적이다라고 말한 게 아닐까 생각하는데
댓글 보면 알겠지만 내가 일반적이라고 한 건 아니라서 몰루..
추가로 정리하면
일단 충돌이 없을수록 이후에 평문으로 비교할 일이 적어지니까 성능상 좋음
충돌이 없다는 건 말이 안된다는 맞음
일반적이냐 아니냐를 따지는건
10000번 중에 몇 번이 있어야 적당한거냐를 따지는 수준의 얘기인 것 같음

펼쳐보기▼

nano

2023-01-07 10:14:42 답글

ㅇㅇ 내 생각을 요약하면 원래 댓글에서 "일반적인 이야기"라고 말한게 "충돌이 전혀 없다"로 받아들여져서 해시 테이블을 위한 해싱의 경우에는 그럴 수 없다 라고 한거임

펼쳐보기▼

호두와몬드

2023-01-07 10:16:40 답글

아 내가 글을 잘못 썼나 ㅋㅋ
나도 아예 없다고 생각했으면 처리 로직을 고민할 필요가 없다고 했겠지??

펼쳐보기▼

nano

2023-01-07 10:22:30 답글

1. 질문자: '충돌이 생겼을때 원하는 값을 어떻게 찾나요?' 라고 물어봄
2. 원래 댓글: 충돌이 생기는건 일반적이지 않아요
3. 나: 해시 테이블을 만들때는 충돌이 생기는게 일반적
4. 너: 충돌이 적고 잘 분산되는게 좋은 알고리즘이니 충돌이 적은게 일반적

펼쳐보기▼

nano

2023-01-07 10:23:20 답글

결국 '일반적'이라는 단어를 서로 다른 의미로 쓰는거 같은데 어쨌든 충돌이 덜 발생할수록 좋지만 아예 없을수는 없으니 그거를 고려 해야한다~가 우리의 공통된 의견아닐까

펼쳐보기▼

호두와몬드

2023-01-07 10:35:07 답글

내가 일반적이라고 한건 아니라.. 어쩌다보니 저 사람은 이랬을 것이다로 얘기한 것 뿐임.. 
왜 변호를 하고 있는지 모르겠는데 
말대로 본질적으론 같은 생각을 하고 있는 듯..

펼쳐보기▼

호두와몬드

2023-01-07 10:27:12 답글

*수정됨

혹시 따지고 싶어서 그러는가 싶어서 말하는데
원래 댓글 : 해시는 충돌 거의 없는데 글쓴이가 뭘 잘못한거다
나 : 충돌 가능성은 해시 알고리즘과 테이블 크기에 따라 다르다
원래 댓글 : 일반적인 경우를 말한거다
에서 나는 이 사람이 뭘 일반적인지 말하는가는 넘어가고
글쓴이는 충돌 시 예외 처리 방법을 고민하는 거니까 그런 답변은 필요가 없다고 한거야
4바이트 데이터가 키값이고 해싱 테이블 인덱스가 10000개면 당연히 충돌이 잦겠지

펼쳐보기▼

nano

2023-01-07 10:36:13 답글

ㅇㅇ

2023-01-07 10:43:07 답글

이론적 문제가 아니라, 실제 서비스 구축 도중의 문제라고 생각하고 답변해버렸네. 오해하게 해서 미안하다

펼쳐보기▼

aa (211.234)

2023-01-07 09:51:36 삭제 수정 답글

*수정됨

예를들어
"hi" -> 3
"hello" -> 3
이고, 오픈어드레스 방식에서 1 더해서
"hello"를 4로 저장한다 치면

다시 검색할때 hello를 해시함수에 넣어도 나오는건 어짜피 3이고 원래 저장한 값은 4에있을거고...
내가 4로 바꿔서 저장했으면 그걸 따라가는게 구현이 되어있나 궁금해서 물어봤어

펼쳐보기▼

nano

2023-01-07 09:53:47 답글

hello로 찾아야지

펼쳐보기▼

aa (211.234)

2023-01-07 09:54:39 삭제 수정 답글

응응 hello로 찾아도 나오는값은 3일거아니야
그 3에 해당하는 벨류가 맞는다는 보장이 없는것같아서

펼쳐보기▼

nano

2023-01-07 09:55:05 답글

아니 시발 3으로 찾지말고 hello로 찾으라고

펼쳐보기▼

aa (211.234)

2023-01-07 09:55:30 삭제 수정 답글

따로 저장해줘야하는구나... 구체적인 구현이 안나와있어서 몰랐어 고마워

펼쳐보기▼

nano

2023-01-07 09:56:32 답글

호두와몬드

2023-01-07 09:54:37 답글

해시테이블을 왜 쓰는지 먼저 생각해보면
많은 데이터가 있을 때 바구니를 나눠서 어느 곳에 있을지를 빨리 알자가 골자임
그래서 오픈 어드레스라면 해시값이 3이었으니까 거기서부터 단조 증가하면서 찾으면 같은게 있겠다고 생각하고 탐색하는 거임

펼쳐보기▼

aa (211.234)

2023-01-07 09:57:17 삭제 수정 답글

빡대가리 이해시켜줘서 감사합니당

펼쳐보기▼

aa (211.234)

2023-01-07 09:57:24 삭제 답글

댓글 작성

업로드 중

0초

녹음 중지 삭제

글쓰기

전체글 개념글

최근 최근 방문 채널

최근 방문 채널

전체 공지 정보 질문 잡담 유머 C/C++ C# Python Java Front-end Back-end 앱·겜 AI·Data 그 외

번호 제목

작성자 작성일 조회수 추천

C++ 기초 공부하면서 깨달은 점 [5]

ㅇㅇ (125.191) 2023.01.08 347 1

잡담 애니미즘 [1]

slash 2023.01.08 102 2

유머 굉장히 중요한 파이썬 모듈 ant [11]

Q9 2023.01.08 952 18

질문 유니티 유지보수를 위해서 [6]

SSeries 2023.01.08 126 0

질문 여기 사람들은 WPF공부 어떻게 했음? [3]

Joker 2023.01.07 182 0

(게임)작은 프로젝트라도 포폴에 넣을수 잇을가 [3]

잔향 2023.01.07 198 2

질문 웹쪽 전혀 모르는 본인 후다닥 웹 만드려는데 어떤 거 공부해야할지 지식좀.. [5]

양가온 2023.01.07 207 0

C/C++ 이동 시맨틱 생성 안 되는 버?그 (Visual Studio 2022) [2]

dummypnguin 2023.01.07 147 0

C# C#은 유니티게임 말고는 사용처가 그닥 없는거임? [7]

오버니삭스 2023.01.07 476 0

질문 히토미 파싱 불가능한거임? [3]

moonhole 2023.01.07 527 0

질문 해시 충돌시에 검색할 때 [40]

aa (211.234) 2023.01.07 211 0

IT 채용시장 2023년 어떨꺼같음...? [13]

악해병당고가너무좋아준코님 2023.01.07 362 0

리캡챠가 지금도 유효할까? [1]

딕웰컴라뷰린스 2023.01.07 110 1

docker 입문자 이거 보셈... [1]

잘되게해주세요 2023.01.06 254 4

Front-end 디자인 패턴 쉽지 않네 [2]

지우개로널지울수만있다면 2023.01.06 184 1

CUDA를 사용하려고 하는데 어떤 언어가 제일 좋음? [3]

ㅇㅇ (175.203) 2023.01.06 163 0

완성.. [6]

보빗보빗보비빗 2023.01.06 517 18

ㅇㅇ (106.101) 2023.01.06 684 12

글쓰기

전체글 개념글