해시 표 에 대하 여

1. 해시 표 정의:
해시 표 는 데이터 구조 로 빠 른 삽입 작업 과 검색 작업 을 제공 할 수 있 습 니 다.하 쉬 시 계 를 처음 접 했 을 때 믿 을 수 없 을 정도 로 장점 이 많 았 다.해시 표 에 데이터 가 얼마나 있 든 지 간 에 삽입 과 삭제 (때로는 사 이 드 제거 포함) 는 상수 에 가 까 운 시간 즉 0 (1) 의 시간 급 만 필요 합 니 다. 실제로 이것 은 몇 개의 기계 명령 만 필요 합 니 다.
해시 표 의 사용자 한 명 에 게 는 순간 적 인 일이 다. 해시 표 는 연산 이 매우 빠르다. 컴퓨터 프로그램 에서 1 초 안에 수천 개의 기록 을 찾 아야 한다 면 해시 표 (예 를 들 어 맞 춤 법 검사 기) 를 사용 하 는 해시 표 의 속도 가 나무 보다 현저히 빠르다. 나무의 조작 은 보통 O (N) 가 필요 하 다.해시 표 는 속도 가 빠 를 뿐만 아니 라 프로 그래 밍 실현 도 상대 적 으로 쉽다.
해시 표 도 기본 과 배열 의 단점 이 있 습 니 다. 배열 을 만 든 후에 일부 해시 표 가 기본적으로 채 워 졌 을 때 성능 이 매우 떨 어 졌 기 때문에 프로그램 은 표 에 얼마나 많은 데 이 터 를 저장 해 야 하 는 지 알 아야 합 니 다 (또는 정기 적 으로 데 이 터 를 더 큰 해시 표 로 옮 길 준 비 를 해 야 합 니 다. 이것 은 시간 이 걸 리 는 과정 입 니 다).
그리고 표 의 데이터 항목 을 어떤 순서 로 든 옮 겨 다 닐 수 있 는 간편 한 방법 도 없다.이런 능력 이 필요 하 다 면 다른 데이터 구 조 를 선택 할 수 밖 에 없다.
그러나 데 이 터 를 질서 있 게 옮 겨 다 닐 필요 가 없다 면 우물 은 데이터 의 크기 를 미리 예측 할 수 있다.그렇다면 해시 시 계 는 속도 와 용이 성에 있어 서 비 길 데 가 없다.
해시 함 수 는 데이터 시퀀스 에 대한 접근 과정 을 더욱 신속 하고 효과적으로 할 수 있 습 니 다. 해시 함 수 를 통 해 데이터 요 소 는 더욱 빠르게 포 지 셔 닝 될 것 입 니 다.
1. 직접 주소 지정 법: 키워드 나 키 워드 를 가 져 오 는 선형 함수 값 은 해시 주소 입 니 다.즉 H (key) = key 또는 H (key) = a · key + b, 그 중에서 a 와 b 는 상수 (이런 해시 함 수 를 자체 함수 라 고 함)
2. 디지털 분석 법
3. 제곱 취 중 법
4. 접 는 법
5. 난수 법
6. 나머지 를 제외 한 방법: 키 워드 를 취 하 는 것 은 산열 표 의 길이 m 보다 크 지 않 은 수의 p 에 의 해 제 거 된 후에 얻 은 나머지 는 산열 주소 이다.즉 H (key) = key MOD p, p < = m.키 워드 를 직접 모델 링 할 수 있 을 뿐만 아니 라 접 기, 제곱 취 중간 연산 후에 도 모델 링 을 할 수 있다.p 에 대한 선택 은 매우 중요 하 다. 일반적으로 소수 나 m 를 취하 는데 p 가 잘 선택 하지 못 하면 동의어 가 생기 기 쉽다.
1. 주소 지정 방법 개방: Hi = (H (key) + di) MOD m, i = 1, 2,..., k (k < = m - 1), 그 중에서 H (key) 는 해시 함수 이 고 m 는 해시 표 길이 이 며 di 는 증분 서열 이 며 다음 세 가지 방법 이 있 습 니 다.
      1. di = 1, 2, 3,..., m - 1 을 선형 탐지 재 산열 이 라 고 한다.
      2. di = 1 ^ 2, (- 1) ^ 2, 2 ^ 2, (- 2) ^ 2, (3) ^ 2,... ± (k) ^ 2, (k < = m / 2) 2 차 탐지 재 산열
     해시 표 는 데이터 구조 로 빠 른 삽입 작업 과 검색 작업 을 제공 할 수 있 습 니 다.하 쉬 시 계 를 처음 접 했 을 때 믿 을 수 없 을 정도 로 장점 이 많 았 다.해시 표 에 데이터 가 얼마나 있 든 지 간 에 삽입 과 삭제 (때로는 사 이 드 제거 포함) 는 상수 에 가 까 운 시간 즉 0 (1) 의 시간 급 만 필요 합 니 다. 실제로 이것 은 몇 개의 기계 명령 만 필요 합 니 다.
해시 표 의 사용자 한 명 에 게 는 순간 적 인 일이 다. 해시 표 는 연산 이 매우 빠르다. 컴퓨터 프로그램 에서 1 초 안에 수천 개의 기록 을 찾 아야 한다 면 해시 표 (예 를 들 어 맞 춤 법 검사 기) 를 사용 하 는 해시 표 의 속도 가 나무 보다 현저히 빠르다. 나무의 조작 은 보통 O (N) 가 필요 하 다.해시 표 는 속도 가 빠 를 뿐만 아니 라 프로 그래 밍 실현 도 상대 적 으로 쉽다.
해시 표 도 기본 과 배열 의 단점 이 있 습 니 다. 배열 을 만 든 후에 일부 해시 표 가 기본적으로 채 워 졌 을 때 성능 이 매우 떨 어 졌 기 때문에 프로그램 은 표 에 얼마나 많은 데 이 터 를 저장 해 야 하 는 지 알 아야 합 니 다 (또는 정기 적 으로 데 이 터 를 더 큰 해시 표 로 옮 길 준 비 를 해 야 합 니 다. 이것 은 시간 이 걸 리 는 과정 입 니 다).
그리고 표 의 데이터 항목 을 어떤 순서 로 든 옮 겨 다 닐 수 있 는 간편 한 방법 도 없다.이런 능력 이 필요 하 다 면 다른 데이터 구 조 를 선택 할 수 밖 에 없다.
그러나 데 이 터 를 질서 있 게 옮 겨 다 닐 필요 가 없다 면 우물 은 데이터 의 크기 를 미리 예측 할 수 있다.그렇다면 해시 시 계 는 속도 와 용이 성에 있어 서 비 길 데 가 없다.
해시 함 수 는 데이터 시퀀스 에 대한 접근 과정 을 더욱 신속 하고 효과적으로 할 수 있 습 니 다. 해시 함 수 를 통 해 데이터 요 소 는 더욱 빠르게 포 지 셔 닝 될 것 입 니 다.
1. 직접 주소 지정 법: 키워드 나 키 워드 를 가 져 오 는 선형 함수 값 은 해시 주소 입 니 다.즉 H (key) = key 또는 H (key) = a · key + b, 그 중에서 a 와 b 는 상수 (이런 해시 함 수 를 자체 함수 라 고 함)
2. 디지털 분석 법
3. 제곱 취 중 법
4. 접 는 법
5. 난수 법
6. 나머지 를 제외 한 방법: 키 워드 를 취 하 는 것 은 산열 표 의 길이 m 보다 크 지 않 은 수의 p 에 의 해 제 거 된 후에 얻 은 나머지 는 산열 주소 이다.즉 H (key) = key MOD p, p < = m.키 워드 를 직접 모델 링 할 수 있 을 뿐만 아니 라 접 기, 제곱 취 중간 연산 후에 도 모델 링 을 할 수 있다.p 에 대한 선택 은 매우 중요 하 다. 일반적으로 소수 나 m 를 취하 는데 p 가 잘 선택 하지 못 하면 동의어 가 생기 기 쉽다.
1. 주소 지정 방법 개방: Hi = (H (key) + di) MOD m, i = 1, 2,..., k (k < = m - 1), 그 중에서 H (key) 는 해시 함수 이 고 m 는 해시 표 길이 이 며 di 는 증분 서열 이 며 다음 세 가지 방법 이 있 습 니 다.
1. di = 1, 2, 3,..., m - 1 을 선형 탐지 재 산열 이 라 고 한다.
2. di = 1 ^ 2, (- 1) ^ 2, 2 ^ 2, (- 2) ^ 2, (3) ^ 2,... ± (k) ^ 2, (k < = m / 2) 를 2 차 탐지 재 산열 이 라 고 한다.
3. di = 위조 난수 서열, 위조 랜 덤 탐지 재 산열 이 라 고 합 니 다. = =
2. 재 산열 법: Hi = RHI (key), i = 1, 2,.
3. 체인 주소 법 (지퍼 법)
저장 구조 가 링크 일 때 지퍼 법 을 많이 사용 하고 지퍼 법 으로 충돌 을 처리 하 는 방법 은 같은 해시 주 소 를 가 진 키워드 (동의어) 값 을 같은 단일 링크 에 넣 어 동의어 링크 라 고 부른다.m 개의 해시 주소 가 있 으 면 m 개의 링크 가 있 고 포인터 배열 T [0. m - 1] 로 각 링크 의 헤드 포인 터 를 저장 합 니 다. 해시 주소 가 i 인 기록 은 모두 결점 방식 으로 T [i] 를 포인터 로 하 는 단일 링크 에 삽 입 됩 니 다.T 의 각 분량 의 초기 값 은 빈 지침 이 어야 합 니 다.해시 표 는 데이터 구조 로 빠 른 삽입 작업 과 검색 작업 을 제공 할 수 있 습 니 다.하 쉬 시 계 를 처음 접 했 을 때 믿 을 수 없 을 정도 로 장점 이 많 았 다.해시 표 에 데이터 가 얼마나 있 든 지 간 에 삽입 과 삭제 (때로는 사 이 드 제거 포함) 는 상수 에 가 까 운 시간 즉 0 (1) 의 시간 급 만 필요 합 니 다. 실제로 이것 은 몇 개의 기계 명령 만 필요 합 니 다.
해시 표 의 사용자 한 명 에 게 는 순간 적 인 일이 다. 해시 표 는 연산 이 매우 빠르다. 컴퓨터 프로그램 에서 1 초 안에 수천 개의 기록 을 찾 아야 한다 면 해시 표 (예 를 들 어 맞 춤 법 검사 기) 를 사용 하 는 해시 표 의 속도 가 나무 보다 현저히 빠르다. 나무의 조작 은 보통 O (N) 가 필요 하 다.해시 표 는 속도 가 빠 를 뿐만 아니 라 프로 그래 밍 실현 도 상대 적 으로 쉽다.
해시 표 도 기본 과 배열 의 단점 이 있 습 니 다. 배열 을 만 든 후에 일부 해시 표 가 기본적으로 채 워 졌 을 때 성능 이 매우 떨 어 졌 기 때문에 프로그램 은 표 에 얼마나 많은 데 이 터 를 저장 해 야 하 는 지 알 아야 합 니 다 (또는 정기 적 으로 데 이 터 를 더 큰 해시 표 로 옮 길 준 비 를 해 야 합 니 다. 이것 은 시간 이 걸 리 는 과정 입 니 다).
그리고 표 의 데이터 항목 을 어떤 순서 로 든 옮 겨 다 닐 수 있 는 간편 한 방법 도 없다.이런 능력 이 필요 하 다 면 다른 데이터 구 조 를 선택 할 수 밖 에 없다.
그러나 데 이 터 를 질서 있 게 옮 겨 다 닐 필요 가 없다 면 우물 은 데이터 의 크기 를 미리 예측 할 수 있다.그렇다면 해시 시 계 는 속도 와 용이 성에 있어 서 비 길 데 가 없다.
해시 함 수 는 데이터 시퀀스 에 대한 접근 과정 을 더욱 신속 하고 효과적으로 할 수 있 습 니 다. 해시 함 수 를 통 해 데이터 요 소 는 더욱 빠르게 포 지 셔 닝 될 것 입 니 다.
1. 직접 주소 지정 법: 키워드 나 키 워드 를 가 져 오 는 선형 함수 값 은 해시 주소 입 니 다.즉 H (key) = key 또는 H (key) = a · key + b, 그 중에서 a 와 b 는 상수 (이런 해시 함 수 를 자체 함수 라 고 함)
2. 디지털 분석 법
3. 제곱 취 중 법
4. 접 는 법
5. 난수 법
6. 나머지 를 제외 한 방법: 키 워드 를 취 하 는 것 은 산열 표 의 길이 m 보다 크 지 않 은 수의 p 에 의 해 제 거 된 후에 얻 은 나머지 는 산열 주소 이다.즉 H (key) = key MOD p, p < = m.키 워드 를 직접 모델 링 할 수 있 을 뿐만 아니 라 접 기, 제곱 취 중간 연산 후에 도 모델 링 을 할 수 있다.p 에 대한 선택 은 매우 중요 하 다. 일반적으로 소수 나 m 를 취하 는데 p 가 잘 선택 하지 못 하면 동의어 가 생기 기 쉽다.
1. 주소 지정 방법 개방: Hi = (H (key) + di) MOD m, i = 1, 2,..., k (k < = m - 1), 그 중에서 H (key) 는 해시 함수 이 고 m 는 해시 표 길이 이 며 di 는 증분 서열 이 며 다음 세 가지 방법 이 있 습 니 다.
1. di = 1, 2, 3,..., m - 1 을 선형 탐지 재 산열 이 라 고 한다.
2. di = 1 ^ 2, (- 1) ^ 2, 2 ^ 2, (- 2) ^ 2, (3) ^ 2,... ± (k) ^ 2, (k < = m / 2) 를 2 차 탐지 재 산열 이 라 고 한다.
3. di = 위조 난수 서열, 위조 랜 덤 탐지 재 산열 이 라 고 합 니 다. = =
2. 재 산열 법: Hi = RHI (key), i = 1, 2,.
3. 체인 주소 법 (지퍼 법)
저장 구조 가 링크 일 때 지퍼 법 을 많이 사용 하고 지퍼 법 으로 충돌 을 처리 하 는 방법 은 같은 해시 주 소 를 가 진 키워드 (동의어) 값 을 같은 단일 링크 에 넣 어 동의어 링크 라 고 부른다.m 개의 해시 주소 가 있 으 면 m 개의 링크 가 있 고 포인터 배열 T [0. m - 1] 로 각 링크 의 헤드 포인 터 를 저장 합 니 다. 해시 주소 가 i 인 기록 은 모두 결점 방식 으로 T [i] 를 포인터 로 하 는 단일 링크 에 삽 입 됩 니 다.T 의 각 분량 의 초기 값 은 빈 지침 이 어야 합 니 다.3. di = 위조 난수 서열 을 위조 랜 덤 탐지 재 산열 이 라 고 한다. 
2. 재 산열 법: Hi = RHI (key), i = 1, 2,.
3. 체인 주소 법 (지퍼 법)
 
저장 구조 가 링크 일 때 지퍼 법 을 많이 사용 하고 지퍼 법 으로 충돌 을 처리 하 는 방법 은 같은 해시 주 소 를 가 진 키워드 (동의어) 값 을 같은 단일 링크 에 넣 어 동의어 링크 라 고 부른다.m 개의 해시 주소 가 있 으 면 m 개의 링크 가 있 고 포인터 배열 T [0. m - 1] 로 각 링크 의 헤드 포인 터 를 저장 합 니 다. 해시 주소 가 i 인 기록 은 모두 결점 방식 으로 T [i] 를 포인터 로 하 는 단일 링크 에 삽 입 됩 니 다.T 의 각 분량 의 초기 값 은 빈 지침 이 어야 합 니 다.
 

#define HASHSIZE 32    


//       

char *keywords[] = {
        "auto", "break", "case", "char", "const", "continue", "default", 
        "do",
        "double", "else", "enum", "extern", "float", "for", "goto", 
        "if",
        "int", "long", "register", "return", "short", "signed", "sizeof", 
        "static",
        "struct", "switch", "typedef", "union", "unsigned", "void", "volatile",
        "while"
};

char keybuf[HASHSIZE][10];
static char val_flag[HASHSIZE];//         


void ClearFlag()
{
    int i;
    
    for (i = 0;i < HASHSIZE;i++)
    {
        val_flag[i] = (HASHSIZE+1);//    

    }
}

//    ，                  

unsigned int hash(char *s)
{
    unsigned int hashval;
    int i = 0;

    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31 * hashval;
    hashval = hashval % HASHSIZE; //    


    while ((val_flag[hashval] != (HASHSIZE+1)) && (i<32))
    {
        i++;
        hashval = (hashval + i)%HASHSIZE;    //    ，    (  )  

    }
    if (i<HASHSIZE)
    {
        printf("
    (%d):     ： %d -- ",hashval,i);
        val_flag[hashval] = hashval; //        

        return hashval;
    }
    return -1;
}

int main(void) 
{
  int i, size, pos;

  size = sizeof(keywords) / sizeof(keywords[0]);//       

 
  //        

  ClearFlag(); 
  for(i = 0;i < size; i++)
     strcpy(keybuf[hash(keywords[i])],keywords[i]);

  //                ，      

  ClearFlag(); 
  for(i = 0; i < size; i++)
  {
    pos = hash(keywords[i]);    
    printf("%-10s: %-3d
", keybuf[pos], pos);
  }

  return 0;
}