Open Addressing 탐색/삭제 연산

linear probing 탐색 연산

순서대로 선형 탐색을 하여 key를 찾고 그에 맞는 값을 리턴해줌 하지만 선형 탐사를 하다가 비어있는 부분을 찾게 된다면 애초에 204 라는 key 가 저장되지 않았음을 뜻한다 . 왜냐면 선형탐사는 순차적으로 비어있는 인덱스를 찾아서 값을 저장해주기 때문임.

linear probing 삭제 연산

hash 함수를 통해서 20이란 값을 받았고, 이를 선형탐사를 통해 하나씩 배회하며 key를 찾는다. 여기서는 순서대로 확인했을 경우 22 번 인덱스에 저장되어있음을 확인 할 수 있다.

*** 중요한점은 선형탐사 중 삭제를 바로 할 경우 인덱스가 비어있게 되는데, 이는 다음 삽입을 하거나 탐사를 할때 빈 인덱스를 보고 값이 저장되지 않았다고 판단할 수 있음
즉 인덱스 22가 채워질때 까지 key 903 는 찾을 수 없게 된다. 그러므로 위와같이 "Deleted"라는 임의의 값을 저장해주면서 문제점을 해결 할 수 있다. 탐사를 멈추지않고 저장된 데이터를 모두 찾을 수 있게됨