한 걸음 한 걸음 알고리즘 (hash 표)

【 성명: 판권 전부, 전재 환영, 상업 용도 로 사용 하지 마 십시오. 연락처: feixiaoxixing @ 163. com]
    hash 표, 때로는 산 목록 이 라 고도 불 린 다.개인 적 으로 hash 시 계 는 링크 와 이 진 트 리 사이 에 있 는 중간 구조 라 고 생각 합 니 다.체인 테이블 의 사용 은 매우 편리 하지만 데이터 찾기 는 매우 번거롭다.이 진 트 리 의 데 이 터 는 엄 격 히 질서 가 있 지만, 이것 은 여러 개의 지침 을 대가 로 한 결과 이다.hash 표 는 데이터 검색 의 편 의 를 만족 시 킬 뿐만 아니 라 같은 시간 에 너무 많은 내용 공간 을 차지 하지 않 고 사용 하기에 도 매우 편리 하 다.
    예 를 들 면, 모든 데 이 터 는 마치 많은 책 과 같다.만약 에 이 책 들 이 한 권 한 권 쌓 인 것 이 라 고 가정 하면 링크 나 선형 표 처럼 전체 데 이 터 는 매우 무질서 하고 혼 란 스 러 워 보일 것 이다. 자신 이 필요 로 하 는 책 을 찾기 전에 많은 조회 과정 을 거 쳐 야 한다.그리고 만약 에 당신 이 모든 책 에 대해 번 호 를 매기 고 이 책 들 을 순서대로 배열 한다 고 가정 하면 당신 이 찾 으 려 는 책 번호 가 n 이 라 고 가정 하면 2 분 의 검색 을 통 해 당신 은 자신 이 필요 로 하 는 책 을 곧 찾 을 수 있 을 것 입 니 다.그러나 모든 종류의 책 이 그리 많 지 않다 고 가정 하면 이 책 들 을 분류 할 수 있 습 니 다. 어떤 것 이 문학 류 이 고 어떤 것 이 예술 류 이 며 어떤 것 이 공과 이 고 어떤 것 이 이과 입 니까? 당신 은 이 책 들 을 간단하게 분류 해 야 합 니 다. 그러면 책 한 권 을 찾 는 것 도 매우 쉬 워 질 것 입 니 다. 예 를 들 어 당신 이 찾 는 책 이 컴퓨터 분야 의 책 이 라 고 가정 하면그러면 공 대 에서 찾 아 보 는 것 도 귀 찮 을 것 이다.
    이런 예 를 들 어 당신 은 잘 알 고 있 습 니까? 위 에서 언급 한 분류 방법 은 사실상 hash 표 의 본질 입 니 다.다음은 간단 한 hash 조작 코드 를 쓸 수 있 습 니 다.
    a) hash 표 와 기본 데이터 노드 정의

typedef struct _NODE
{
	int data;
	struct _NODE* next;
}NODE;

typedef struct _HASH_TABLE
{
	NODE* value[10];
}HASH_TABLE;

    
b) 해시 테이블 만 들 기

HASH_TABLE* create_hash_table()
{
	HASH_TABLE* pHashTbl = (HASH_TABLE*)malloc(sizeof(HASH_TABLE));
	memset(pHashTbl, 0, sizeof(HASH_TABLE));
	return pHashTbl;
}

    
c) hash 표 에서 데 이 터 를 찾 습 니 다.

NODE* find_data_in_hash(HASH_TABLE* pHashTbl, int data)
{
	NODE* pNode;
	if(NULL ==  pHashTbl)
		return NULL;

	if(NULL == (pNode = pHashTbl->value[data % 10]))
		return NULL;

	while(pNode){
		if(data == pNode->data)
			return pNode;
		pNode = pNode->next;
	}
	return NULL;
}

    
d) hash 표 에 데 이 터 를 삽입 합 니 다.

STATUS insert_data_into_hash(HASH_TABLE* pHashTbl, int data)
{
	NODE* pNode;
	if(NULL == pHashTbl)
		return FALSE;

	if(NULL == pHashTbl->value[data % 10]){
		pNode = (NODE*)malloc(sizeof(NODE));
		memset(pNode, 0, sizeof(NODE));
		pNode->data = data;
		pHashTbl->value[data % 10] = pNode;
		return TRUE;
	}

	if(NULL != find_data_in_hash(pHashTbl, data))
		return FALSE;

	pNode = pHashTbl->value[data % 10];
	while(NULL != pNode->next)
		pNode = pNode->next;

	pNode->next = (NODE*)malloc(sizeof(NODE));
	memset(pNode->next, 0, sizeof(NODE));
	pNode->next->data = data;
	return TRUE;
}

    
e) hash 표 에서 데이터 삭제

STATUS delete_data_from_hash(HASH_TABLE* pHashTbl, int data)
{
	NODE* pHead;
	NODE* pNode;
	if(NULL == pHashTbl || NULL == pHashTbl->value[data % 10])
		return FALSE;

	if(NULL == (pNode = find_data_in_hash(pHashTbl, data)))
		return FALSE;

	if(pNode == pHashTbl->value[data % 10]){
		pHashTbl->value[data % 10] = pNode->next;
		goto final;
	}

	pHead = pHashTbl->value[data % 10];
	while(pNode != pHead ->next)
		pHead = pHead->next;
	pHead->next = pNode->next;

final:
	free(pNode);
	return TRUE;
}

요약:
    1. hash 표 는 복잡 하지 않 습 니 다. 우 리 는 개발 에서 도 자주 사용 합 니 다. 친구 들 이 잘 파악 하 는 것 을 권장 합 니 다.
    2. hash 표 는 이 진 트 리 와 복합 구 조 를 형성 할 수 있 습 니 다. 왜 그런 지 여러분 들 이 잘 생각해 보 세 요.