ハッシュについて

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。
BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF
トピックのレビュー
   

展開ビュー トピックのレビュー: ハッシュについて

Re: ハッシュについて

#6

by かずま » 5年前

ハッシュ値 18 が表示されないというバグがありました。
if (k != h) { を
if (k != h || i == n-1) { に修正します。

なお、text.txt は 84個の単語があり、
ハッシュ値が 8 になったのは vendor だけだったので、
これは重複がありません。
オフトピック
なぜ、何も応答しない質問者が多いのだろうか？

Re: ハッシュについて

#5

by かずま » 5年前

すみません。word の表示が間違っていました。
次のように訂正します。

コード: 

				printf("%s", word[index[j]]);
				while (++j < i) printf(", %s", word[index[j]]);
実行結果

コード: 

language, many, memory, program が 0 で衝突
provide, software が 1 で衝突
can, implement, instruction, minimal, static, variable が 2 で衝突
and, cross, encourage, machine, purpose, ritchie が 3 で衝突
compiler, level, standardized が 4 で衝突
between, computer, former, majority, require, while が 5 で衝突
mind, scope, unintended が 6 で衝突
design, structured, wide が 7 で衝突
all, ansi, assembly, despite が 9 で衝突
efficient, use が 10 で衝突
become, been, source が 11 で衝突
code, general, includ, prevent, range, straightforward, system, variety が 12 で衝突
application, institute, see, standard, time, type が 13 で衝突
imperative, map, most, platform, therefore が 14 で衝突
american, low, microcontroller, that, unix が 15 で衝突
bell, lexical が 16 で衝突
available, compliant, original, since, typical, various, very が 17 で衝突

Re: ハッシュについて

#4

by かずま » 5年前

入力時にハッシュ値でソートして、
出力時に同じハッシュ値のものを表示すればよいのではありませんか？

コード: 

#include <stdio.h>   // fopen, fclose, fgets, printf
#include <string.h>  // strchr

#define WORD_MAX  100
#define WORD_SIZE 256

unsigned int MakeHash1(const char *str, unsigned int hashmax)
{
	unsigned int hash = 0;

	for (int i = 0; str[i]; i++) hash += str[i];
	return hash % hashmax;
}

int main(void)
{
	char word[WORD_MAX][WORD_SIZE], *p;
	unsigned hash[WORD_MAX];
	int index[WORD_MAX], i, j, k, h, n;

	FILE *fp = fopen("text.txt", "r");
	if (fp == NULL) return printf("ファイルオープンエラー\n"), 1;

	for (n = 0; n < WORD_MAX && fgets(word[n], WORD_SIZE, fp); n++) {
		if (p = strchr(word[n], '\n')) *p = '\0';
		hash[n] = MakeHash1(word[n], 19);
		index[n] = n;
		for (i = n; i > 0 && hash[index[i-1]] > hash[n]; i--)
			index[i] = index[i-1];
		index[i] = n;
	}
	fclose(fp);

	if (n) j = 0, h = hash[index[j]];
	for (i = 1; i < n; i++) {
		k = hash[index[i]];
		if (k != h) {
			if (j < i-1) {
				printf("%s", word[j]);
				while (++j < i) printf(", %s", word[j]);
				printf(" が %d で衝突\n", h);
			}
			j = i, h = k;
		}
	}
}
text.txt

コード: 

access
all
american
and
ansi
application
assembly
available
become
been
bell
between
can
code
compiler
compliant
computer
cross
design
designed
despite
efficient
encourage
few
former
general
imperative
implement
includ
institute
instruction
language
level
lexical
low
machine
majority
many
map
memory
microcontroller
mind
minimal
most
national
one
original
platform
prevent
program
provide
purpose
range
require
ritchie
run
scope
see
since
software
source
standardized
standard
static
straightforward
structured
support
system
that
therefore
time
type
typical
unintended
unix
use
variable
variety
various
vendor
very
well
while
wide
実行結果

コード: 

access, all, american, and が 0 で衝突
ansi, application が 1 で衝突
assembly, available, become, been, bell, between が 2 で衝突
can, code, compiler, compliant, computer, cross が 3 で衝突
design, designed, despite が 4 で衝突
efficient, encourage, few, former, general, imperative が 5 で衝突
implement, includ, institute が 6 で衝突
instruction, language, level が 7 で衝突
low, machine, majority, many が 9 で衝突
map, memory が 10 で衝突
microcontroller, mind, minimal が 11 で衝突
most, national, one, original, platform, prevent, program, provide が 12 で衝突
purpose, range, require, ritchie, run, scope が 13 で衝突
see, since, software, source, standardized が 14 で衝突
standard, static, straightforward, structured, support が 15 で衝突
system, that が 16 で衝突
therefore, time, type, typical, unintended, unix, use が 17 で衝突
このプログラムが参考になれば、分かりやすいプログラムに書き換えて
提示してください。
質問は何でも受け付けます。

Re: ハッシュについて

#3

by k_asu » 5年前

返信いただいたコードにより衝突は分かったのですが、例えばabout, some, good132で衝突」のようにprintfしたいです。
自分がかいたコードではそれが実現できていないので、アドバイスお願いします。

コード: 

	for (i = 0; i < 100; i++) {
		for (j = 0; j < 100; j++) {

			if (MakeHash_table[i] == MakeHash_table[j] && i != j) {
				printf("%d番目の%sで衝突しました\n", i, Lines[i]);
			}
		}
	}

Re: ハッシュについて

#2

by littlestream » 5年前

ハッシュではないですが配列に入れた乱数の重複を調べるなら二重ループで

コード: 

if(MakeHash_table[i]==MakeHash_table[j] && i!=j)
という条件で判定するプログラムはどうでしょうか

ハッシュについて

#1

by k_asu » 5年前

現在、テキストから読み込んだ英単語100個をハッシュ値を求めて、それを配列にいれて同じ値を探したいと考えています。

そこで、配列にいれたハッシュ値の重複を表示する方法がわからないのでわかるかたは教えてください

コード: 


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define HASHMAX 100
#define LineMax 100
#define N 100

unsigned int MakeHash1(char* str, unsigned int hashmax);

int main(void){

   FILE * fp;
   char Lines[LineMax][256];
   char MakeHash_table[N]
   unsigned int i;
   int j,k,count_MakeHash;

   fp = fopen("text.txt","r");
   if( fp == NULL ){
   printf( "ファイルオープンエラー\n" );
   return -1;
   }

   for(i=0; i<LineMax && fgets( Lines[i] , sizeof(Lines[i]) , fp ) != NULL;i++){
  
     // printf( "Lines[%d]=%s", i,Lines[i] );
   }

fclose( fp );

 for(i=0;k<100;k++){
 
  MakeHash_table[k] = count_MakeHash = MakeHash1(Lines[k],19);

 }

 
 return 0;
}

unsigned int MakeHash1(char* str, unsigned int hashmax) {
    unsigned int n, length, hash;

    length = strlen(str);
    for(n = 0, hash = 0; n < length; n++) {
        hash += (int)str[n];
    }

    return hash % hashmax;
}

ページトップ