C 해시 찾기 실현

빠 른 찾기 용 C 해시 찾기
한 무더기 의 데이터 에서 특정한 데 이 터 를 포함 하고 있 는 지, 가장 많이 사용 되 는 선형 검색, 보초병 검색, 2 분 검색 (정렬 되 어 있 으 면) 을 찾 습 니 다. 그러나 이 검색 방법 들 은 적어도 O (logN) 의 복잡 도 입 니 다. 메모리 가 충분 하고 해시 함수 가 합 리 적 으로 구축 되 어 있다 면 하 쉬 를 사용 하여 다른 검색 알고리즘 을 순식간에 죽 일 수 있 습 니 다. 시간 복잡 도 는 O (1) 밖 에 없습니다.
요약 하면 일반적으로 우 리 는 한 무더기 의 데이터 (예 를 들 어 한 무더기 의 정수) 가 있 습 니 다. 우 리 는 보통 그들 중의 한 속성 (그 값 크기) 을 통 해 우리 가 찾 고 싶 은 (정수) 가 이 정수 에 존재 하 는 지 판단 합 니 다. 그러나 하나의 변 수 는 우리 가 주목 할 수 있 는 세 가지 속성 이 있어 야 합 니 다.

변수 명

저 장 된 주소

변수의 값

예 를 들 어 선형 검색, 하나의 순환, 모든 변수 이름 에 대응 하 는 값 이 우리 가 찾 고 싶 은 값 과 같 는 지 여 부 를 계속 판단 합 니 다. 즉, 우 리 는 이 값 이 저 장 된 위 치 를 알 수 없고 순서 가 있 고 중복 되 지 않 는 한 개의 반복 이 필요 합 니 다. 찾 을 때 까지.
그러나 하 쉬 가 찾 는 것 은 이 데이터 의 저장 주소 에 착안 한 것 이다. 즉, 모든 데 이 터 를 어디 에 저장 해 야 하 는 지 이미 알 고 있다 는 것 이다. 당신 이 해 야 할 일 은 메모리 에 있 는 이 위치 에 물건 이 있 는 지 보 는 것 이다. 있 으 면 찾 았 다 는 것 을 설명 하고 없 으 면 이 데이터 에 우리 가 찾 고 싶 은 데이터 가 없다 는 것 을 설명 한다.
예 를 들 어 (메모리 위치 가 정확 하지 않 고 간결 함 을 설명 하기 위해 서): 저 에 게 데이터 가 한 무더기 있 습 니 다. 1, 2, 3, 34, 36, 23, 4, 12, 654, 8732 그러면 저 는 이렇게 저장 할 수 있 습 니 다.
1
2
3
34
36
0x00000010
0x00000014
0x0000001E
0x00000154
0x00000168
23
4
12
654
8732
0x000000E6
0x00000028
0x00000078
0x0000198C
0x00015518
모든 변수 가 저장 하 는 주 소 는 그 값 의 10 배 입 니 다. 우리 가 변 수 를 찾 으 려 고 할 때 그 값 을 10 으로 곱 하고 결 과 를 지침 에 부여 한 다음 에 이 지침 이 가리 키 는 값 이 우리 가 찾 고 싶 은 값 인지 아 닌 지 를 판단 합 니 다. 만약 에 이 데이터 에 저장 되 어 있다 는 것 을 설명 합 니 다. 그렇지 않 으 면 이 데이터 에 없 음 을 설명 합 니 다.
값 의 해시 값 을 어떻게 가 져 오 는 지 에 대해 서 는 더 이상 설명 하지 않 습 니 다. 다음은 하나의 예 입 니 다. 예 를 들 어 사용 하 는 배열 은 메모리 의 주 소 를 모 의 하고 해시 값 을 가 져 오 는 데 나머지 방법 을 사용 합 니 다.
C + + 의 컴 파 일 러 를 사용 하기 때문에 c + + 의 프로젝트 입 니 다. 그러나 핵심 문법 은 모두 C 로 작 성 된 것 입 니 다. C + + 의 부분 은 많이 언급 되 지 않 았 습 니 다. 본 예 에서 사용 하 는 것 은 하나의 링크 구조 입 니 다. 각 노드 에는 다음 노드 를 가리 키 는 지침 과 유일한 정수 가 포함 되 어 있 습 니 다.

#include "pch.h"
#include 
using namespace std;
#define Length 10 // the number of the node

struct node
{
  int value;
  struct node* next;
};//the node

struct hash_map {
  struct node** link_list; // use a pointer which point a pointer to ensure its a link list
  int count;
};//the hash_map


void init(hash_map *hashmap) {
  hashmap->link_list = (node**)malloc(Length * sizeof(node*));
  hashmap->count = Length;

  for (int i = 0; i < Length; i++) {
    hashmap->link_list[i] = (node*)malloc(Length * sizeof(node));

  }
  for (int i = 0; i < Length; i++) {
    hashmap->link_list[i]->value = NULL; // give a inital value of every node
    if (i != Length - 1)				//make the node array become a link list
      hashmap->link_list[i]->next = hashmap->link_list[i + 1];
    else
      hashmap->link_list[i]->next = nullptr;
  }
}//init the hash_map

int get_hash(int value,hash_map* hashmap) {
  return value % hashmap->count;
}// get the hash value of a node


void enlargeSpace(hash_map* hashmap) {
  hashmap->count = 2 * hashmap->count;
  int *arr = (int*)malloc(hashmap->count * sizeof(int));
  for (int i = 0; i < hashmap->count; i++) {
    arr[i] = NULL;
  }
  int hash;
  for (int i = 0; i < hashmap->count / 2; i++) {
    hash = get_hash(hashmap->link_list[i]->value, hashmap);
    while (arr[hash] != NULL) {
      hash = get_hash(++hash, hashmap);
    }
    arr[hash] = hashmap->link_list[i]->value;
  }
  hashmap->link_list = (node**)malloc(hashmap->count*sizeof(node*));
  for (int i = 0; i < hashmap->count; i++) {
    hashmap->link_list[i] = (node*)malloc(sizeof(node));
    hashmap->link_list[i]->value = arr[i];
  }
  for (int i = 0; i < hashmap->count; i++) {
    if (i != hashmap->count - 1)				//make the node array become a link list
      hashmap->link_list[i]->next = hashmap->link_list[i + 1];
    else
      hashmap->link_list[i]->next = nullptr;
  }

}// enlarge the space of the array

int createHashMap(int data,hash_map* hashmap) {
  for(int i = 0;i<hashmap->count;i++)
    if(hashmap->link_list[i]->value==NULL)
      goto a;
  enlargeSpace(hashmap);//if there is no more space
a:
  int hash_value = get_hash(data,hashmap); // get the hash value of the node's value
  while (hashmap->link_list[hash_value]->value != NULL) { // if there is a value in the address, re-hash it
    hash_value = get_hash(++hash_value,hashmap);
  }
  hashmap->link_list[hash_value]->value = data; // store the value of the node in to the hash_map
  return 0;
}//create Hash Map


int find(hash_map* hashmap,int data) {
  int hash_value = get_hash(data,hashmap);
  int tempData = data;
  int first_hash_value = hash_value;
  while (hashmap->link_list[hash_value]->value != data) {
    tempData++;
    hash_value = get_hash(tempData,hashmap);
    if (hashmap->link_list[hash_value]->value == NULL || first_hash_value == hash_value)// if we do not find the data, return -1
      return -1;
  }
  return hash_value;

}

void removeNode(hash_map* hashmap, int hash_value) {
  if (hash_value == -1) // if the value is not in the link list
    return;
  hashmap->link_list[hash_value - 1]->next = hashmap->link_list[hash_value]->next;
  hashmap->link_list[hash_value] = nullptr;
}

int main()
{
  int arr[10] = { 1, 3, 4, 23, 64, 423,5643,543, 21, 123 };
  hash_map hashmap;
  node* head;

  head = (node*)malloc(sizeof(node));

  init(&hashmap);
  int j = 0;
  while (j < Length) {
    if (hashmap.link_list[j] != nullptr) {

      head = hashmap.link_list[j];
      break;
    }
    j++;
  }//ensure the head is the first one of the link list

  for (int i = 0; i < Length; i++)
    createHashMap(arr[i],&hashmap);
  for (int i = 300000; i < 300020; i++)
    createHashMap(i,&hashmap);
  printf("the init link list is:
");

  while (head != nullptr) {
    printf("%d\t", head->value);
    head = head->next;
  }//print the link list before we remove anyone
  j = 0;

  while (j < Length) {
    if (hashmap.link_list[j] != nullptr) {

      head = hashmap.link_list[j];
      break;
    }
    j++;
  }//ensure the head is the first one of the link list


  removeNode(&hashmap, find(&hashmap, 423));
  removeNode(&hashmap, find(&hashmap, 1));

  printf("
 After remove a node:
");
  while (head != nullptr) {
    if(head->value!=NULL)
      printf("%d\t", head->value);
    head = head->next;
  }//print the result of the link list after we remove 423 and 1

}