ΥڡϤƤʥ֥åޡɲΥڡޤϤƤʥ֥åޡ Υڡlivedoor åפɲΥڡޤlivedoor å

ܼ

ǡõ

ǡ¤ǤȤŪõǡȰפܤõФƤȤǡõȤǡοʤñõƤäƤ褤󤢤Ϲ®ˡͤʤФʤʤ

õˡ

õˡȤϡǡǽ餫֤ˤҤȤĤӤơŪΥǡõФ르ꥺǤ롣ǡõǤäȤñˡǤ롣õФǡϡ¤ǤƤõǤ롣

õˡǤϡΤ褦ʥ르ꥺõԤ

1ǽA(1)ϤơõǡXȽӤ롣

2A(k)õǡXȰפ硢kܤӤõλ롣

3A(k)1knϰϤǥǡXȰפʤ硢nkȤʤäƥ롼פλ롣

㡧10ĤΥ桼̾ܤƤƥȥե뤫顢õˡȤäõǡǤipusironפõƤ

Ǥ7ܤӤŪΥ桼̾õλǤ롣

õԤݤˡפǡ¸ߤʤνλȤơκǸõǡղä뤳Ȥ롣ղǤΤȤʼڤФؤȤǡnʤСn+1ܤʼ֤櫓Ǥ롣

㡧ۤɤʼ֤

ʤʼʤɤȤΤͤΤȤȡʼѤʤȤ롼פνꡢ᤯ʤ뤫Ǥ롣

õˡħ

  • å
    • 르ꥺबñǤ롣
    • ǡɤʽ֤¤ǤȤƤõȤǤ롣ĤޤꡢǡȤƤʤƤס
  • ǥå
    • ǰξ硢٤ƤΥǡĴ٤ʤФʤʤ
    • Ϳ줿ǡõоݤΥǡʤƤ⡢٤ƤΥǡĴ٤Ƥޤ
    • Ϳ줿ǡõоݤΥǡʣäȤƤ⡢ǽΥǡĤʤ

õˡή

Ƶ򼡤Τ褦롣

  • iǤֹ
  • nǿ
  • Xõǡ

ʼѤʤ

ʼѤ

õˡΥ르ꥺ

õԤ르ꥺͤ롣

  • Input: dataõоݤȤʤǡ,nõ͡
  • Output: yʸĤäֹ档Ĥʤä-1
  1
  2
  3
  4
  5
  6
for i=0,,length(data) do
    if data[i]==n do
        yi
        return y
y-1
return y

õˡη׻

ǡnΤȤõϼ̤Ǥ롣

  • Ǿõ1
  • õn
  • ʿõ(n+1)/2

õˡǤϼ¹Ի֤ǿn㤹Τǡ׻̤ΥO~\(~n~\)Ǥ롣

¸

JavaȤäõˡμ¸

õˡ¹Ԥ륢르ꥺLSearch᥽åɤȤͼ¸򤷤Ƥߤ롣¸ѤΥץLinearSearch.javaˤϡ餫data˥åȤͤ椫顢ǻꤷͤõץǤ롣

Everything is expanded.Everything is shortened.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 
 
 
 
 
-
|
|
|
|
|
-
-
-
|
|
!
!
|
|
!
|
|
-
|
|
|
-
|
|
-
|
-
|
|
!
|
|
|
|
|
-
|
!
|
|
|
|
|
|
-
|
-
|
!
!
!
/*
 * LinearSearchõˡΥץ
 * ϡõ
 * ϡĤäֹ
 */
public class LinearSearch {
    
    //õѤΥ᥽å
    //dataõоݤȤʤǡ
    //nõо
    //͡ĤäֹʸĤʤ-1
    static int LSearch(int[] data,int n){
        for(int i=0;i < data.length;i++){
            if(data[i]==n){
                //Ĥä롼פλ
                return i;
            }
        }
        //Ĥʤä-1֤
        return -1;
    }
 
    //main
    public static void main(String[] args) {
        int[] data;    //ǡ
        int n=0;    //õ
        
        if(args.length != 1){
            System.out.println("LinearSearch <n> nõ");
            return;
        }try{
            n=Integer.parseInt(args[0]);
        }catch(NumberFormatException e){
            System.out.println("ͤ˻ꤷƤ");
            return;
        }
        
        //ǡ˥åȤ
        data = new int[] {55,10,20,42,98,71,28,40,67,99};
        
        //Υǡɽ
        for(int k=0;k < data.length;k++){
            System.out.println("data["+k+"] = "+data[k]+"\t");
        }
        System.out.println("");
        
        //ͤõ
        int m=LSearch(data,n);
        
        //̤ɽ
        if(m >= 0){
            System.out.println(n+"ֹ"+m+"Ǥ");
        }else{
            System.out.println(n+"ϸĤޤǤ");
        }
    }
}

¹ϼΤ褦ˤʤ롣

>java LinearSearch 67
data[0] = 55
data[1] = 10
data[2] = 20
data[3] = 42
data[4] = 98
data[5] = 71
data[6] = 28
data[7] = 40
data[8] = 67
data[9] = 99
67ֹ8Ǥ

>java LinearSearch 56
data[0] = 55
data[1] = 10
data[2] = 20
data[3] = 42
data[4] = 98
data[5] = 71
data[6] = 28
data[7] = 40
data[8] = 67
data[9] = 99
56ϸĤޤǤ

ʼѤõˡΥץ˽ˤϡLSearch᥽åɤ򼡤Τ褦˽Ф褤

Everything is expanded.Everything is shortened.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
-
|
|
|
|
|
|
-
|
!
|
|
-
|
!
|
|
|
!
static int LSearch(int[] data,int n){
    //ʼsentinelˤ򥻥å
    int sentinel=data.length-1;
    data[sentinel]=n;
 
    //ǡõ
    int i;
    for(i=0;data[i] != n;i++){
        ;    //⤹뤳ȤϤʤ
    }
 
    //Ĥäֹ椬ʼ
    if(i < sentinel){
        return i;
    }
 
    //ǤʤиĤʤ
    return -1;
}

ޤץdataκǸ0ɲä롣

data = new int[] {55,10,20,42,98,71,28,40,67,99,0};	//Ǹ0ɲ

Хʥꥵʬˡ

ХʥꥵʬˡȤϡõϰϤ򼡡2ʬõϰϤ򶹤ơǽŪΥǡ򸫤ĤФˡǤ롣ǡϾ礫߽ƤʤФʤʤ

ХʥꥵǤϡΤ褦ʥ르ꥺõԤ

1ޤǽˡƬ1nͤбǡǡˤȡõǡXȤӤ롣

2õǡXǤ礭ϡǤ礭ʥǡǤӤ롣õǡXǤ꾮ϡǤ꾮ʥǡǤӤ롣

3A(k)1knϰϤǥǡXȰפʤ硢nkȤʤäƥ롼פλ롣

õоݤ֤¤ǤΤǡƬõΤǤϤʤ椫õõƤͤˤõλǤ롣ʤС¦¦Τ줫Ǥ롣ͤ⾮к¦礭б¦Ȥʤ롣ȡõʤФʤʤǡο쵤ȾʬˤʤäƤޤ櫓Ǥ롣줬ХʥꥵᤤͳǤ롣

Хʥꥵħ

  • å
    • õ®٤®
  • ǥå
    • õоݤΥǡ򤢤餫᥽ȤƤʤФʤʤ

Хʥꥵή

Ƶ򼡤Τ褦롣

  • iǤֹ
  • nǿ
  • Xõǡ
  • LλǤõϰϤǡǤ⾮Ǥֹ
  • HλǤõϰϤǡǤ礭Ǥֹ

ХʥꥵΥ르ꥺ

  • 르ꥺࡧBinary-Search(S,k,p,r)
  • InputAȺѤߤkp,rݥ
  • Outputy s.t. k=key[y]A (or NIL if y¸ߤʤ)
  1
  2
  3
  4
  5
  6
  7
  8
  9
if kkey[r] or kkey[p] then
    return NIL
y=floor_function((p+r)/2)
if k=key[y] then
    return y
else if kkey[y] then
    return Binary-Search(S,k,p,y-1)
else
    return Binary-Search(S,k,y+1,r)

Хʥꥵη׻

ǡnΤȤӲϼ̤Ǥ롣

  • õ\[~\log_2~n~\]~+1
  • ʿõ\[~\log_2~n~\]

Binary-Search(S,k,p,r)η׻̤ϼΤ褦ˤʤ롣

T~\(~n~\)~=~T~\(~\frac{n}{2}~\)~+~O~\(~1\)

Master TheoremȤСΤ褦˷׻Ǥ롣

T~\(~n~\)~=~\Theta~\(~\log~n\)

äơХʥꥵη׻̤ΥO~\(~\log~n~\)Ǥ롣

㡧Ģ100ܤȤ¿Ȥ20ǥǽȤȤˤʤ롣

¸

JavaȤäХʥꥵμ¸

õˡμ¸ǻȤäJavaץõˡ᥽åɤХʥꥵ᥽åɤѹƤߤBinarySearch.javaˡǡƱ10Ǥ뤬ͤϾ¤٤ޤõl,m,rͤõɽ褦ˤƤ롣

Everything is expanded.Everything is shortened.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 
 
 
 
 
-
|
|
|
|
|
-
|
|
|
|
|
-
|
|
|
|
|
|
-
|
-
|
-
|
!
!
|
|
|
!
|
|
-
|
|
|
-
|
|
-
|
-
|
|
!
|
|
|
|
|
-
|
!
|
|
|
|
|
-
|
-
|
!
!
!
/*
 * BinarySearchХʥꥵΥץ
 * ϡõ
 * ϡĤäֹ
 */
public class BinarySearch {
    
    //ХʥꥵѤΥ᥽å
    //dataõоݤȤʤǡ
    //nõо
    //͡ĤäֹʸĤʤ-1
    static int BinarySearch(int[] data,int n){
        //ǡõ
        int cnt=0;    //֤
        int l=0;
        int r=data.length-1;
        //lr꾮ַ֤
        while(l <= r){
            //ͤ
            int m=(l+r)/2;
            
            cnt++;
            System.out.println(cnt+":l="+l+" m="+m+" r="+r);
            
            if(n < data[m]){        //m꺸¦ˤ
                r=m-1;
            }else if(data[m] < n){    //m걦¦ˤ
                l=m+1;
            }else{                    //data[m]==nΤȤ¨ĤäȤ
                return m;
            }
        }
        
        //Ĥʤä-1֤
        return -1;
    }
 
    //main
    public static void main(String[] args) {
        int[] data;    //ǡ
        int n=0;    //õ
        
        if(args.length != 1){
            System.out.println("LinearSearch <n> nõ");
            return;
        }try{
            n=Integer.parseInt(args[0]);
        }catch(NumberFormatException e){
            System.out.println("ͤ˻ꤷƤ");
            return;
        }
        
        //ǡ˥åȤ
        data = new int[] {10,20,28,40,42,55,67,71,98,99};
        
        //Υǡɽ
        for(int k=0;k < data.length;k++){
            System.out.println("data["+k+"] = "+data[k]);
        }
        
        //ͤõ
        int m=BinarySearch(data,n);
        
        //̤ɽ
        if(m >= 0){
            System.out.println(n+"ֹ"+m+"Ǥ");
        }else{
            System.out.println(n+"ϸĤޤǤ");
        }
    }
}

¹Է̤ϼ̤Ǥ롣

> java BinarySearch 99
data[0] = 10
data[1] = 20
data[2] = 28
data[3] = 40
data[4] = 42
data[5] = 55
data[6] = 67
data[7] = 71
data[8] = 98
data[9] = 99
1:l=0 m=4 r=9
2:l=5 m=7 r=9
3:l=8 m=8 r=9
4:l=9 m=9 r=9
99ֹ9Ǥ

õˡʤ99õΤ˺ǰ10õʤФʤʤХʥꥵǤ¿Ƥ4õǤ롣ʤʤС1024ʡ16ˤǤ롣

MathematicaȤäХʥꥵμ¸

MathematicaǥХʥꥵδؿǤBinarySearch[list,elem]ȼΤ褦˥ɤˤʤ롣

  1
  2
  3
  4
  5
  6
  7
  8
  9
BinarySearch[list_,elem_]:=
	Module[{n0=1,n1=Length[list],m=0},
		While[n0<=n1,
			m=Floor[(n0+n1)/2];
			If[list[[m]]==elem,Return[m]]; (* found *)
			If[list[[m]]<elem,n0=m+1,n1=m-1]
		];
		0 (* not found *)
]
 

[]Possible spelling errorפȤ顼ɽ뤫⤷ʤlistΥڥ뤬Listδְ㤤ǤϤʤMathematica¦ڤ˶Ƥ줿˲᤮ʤΤǡ̵뤷Ƥʤ

㡧Τ褦˼¹ԤȡȤ{1,3,5,7,9}ʥȺѤߤǤ뤫OKˤͿơ7õȡ4ܤˤȤȤ狼롣ޤ10õȡ0ɽ¸ߤʤȤ狼롣

ۤɤδؿBinarySearch[list,elem]ˡ르ꥺư򸫤뤿Pring[]ޥɤ롼Τ򡢴ؿBinarySearch2[list,elem]Ȥ롣

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
BinarySearch2[list_,elem_]:=
	Module[{n0=1,n1=Length[list],m=0},
		Print[{n0,n1}];
		While[n0<=n1,
			m=Floor[(n0+n1)/2];
			If[list[[m]]==elem,Return[m]]; (* found *)
			If[list[[m]]<elem,n0=m+1,n1=m-1]
			Print[{n0,n1}];
		];
		0 (* not found *)
]
 

㡧n0n1κǽȳȿθͤ򸫤Ƥߤ롣5õȤϡ3ܤȯƤ롣10Τ褦ǤʤȤϡ르ꥺ礭ʲȿפƤ뤳Ȥ狼롣

ؿBinarySearch[list,elem]ˡAppendTo[]ޥɤ뤳ȤǺǽŪ˥ꥹȤϤ褦˲¤롣BinarySearch3[list,elem]Ȥ롣

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
BinarySearch3[list_,elem_]:=
	Module[{ n0=1,n1=Length[list],m=0,res={} },
		AppendTo[res,{n0,n1}];
		While[n0<=n1,
			m=Floor[(n0+n1)/2];
			If[list[[m]]==elem,Break[]];
			If[list[[m]]<elem,n0=m+1,n1=m-1]
			AppendTo[res,{n0,n1}];
		];
		res
]
 

ɤΤ褦˶֤ʤޤƤ뤫򥰥եɽȻפ

1ޤ1100,000ޤǤ񤫤ƤꥹlʾʸΥˤ롣

l=Range[100000];

2ꥹl¸ߤʤʤǤ7500.5ˤõ롣

pairs=BinarySearch3[l,7500.5]

̤Ȥõn0n1ΥڥΥꥹȤФ롣

{{1,100000},{1,49999},{1,24999},{1,12499},{6251,12499},
{6251,9374},{6251,7811},{7032,7811},{7422,7811},{7422,7615},
{7422,7517},{7470,7517},{7494,7517},{7494,7504},{7500,7504},
{7500,7501},{7501,7501},{7501,7500}}

3õƤ֤бĹ롣(n0,i-1/2)ǡ夬(n1,i)Ǥ롣

Table[Rectangle[{pairs[[i,1]],-i+1/2},{pairs[[i,2]],-i}],
	{i,Length[pairs]}
];

4ǸShowޥɤĹɽ롣

Show[Graphics[%],
	Axes->None,
	Frame->True,
	AspectRatio->1/3,
	PlotRange->All];

ϤϼΤ褦ˤʤäơ֤ʤǤɤΤ褦ȾʬˤʤäƤ狼롣

ϥåˡʥϥåɽõ

ϥåˡʥϥåɽõϡǡ®õ뤿ˡΤҤȤĤǡǡǼݤˤΥɥ쥹ϥåؿǷ׻롣ϥåؿǷ׻줿ͤΤȤϥåȤΥϥåͤѤ뤳Ȥǡǡõݤˤ֤ṳ̂뤳ȤǤ롣

㡧äñˤ뤿ˡϥåؿmod 10Ƿ׻1ץ饹ؿȤ롣ϥåɽκǸH(10)ȤƤΤǡǡ+11ܤܤƹͤΤǤϤʤǡ1ܤܤƤ1äȤƹͤ롣

ϥåˡϤ餫ϥåؿѤƳǼ֤ƤΤǡǡФۤ1ӤõФȤǤ롣

Υ˥

ǡǼȤˡۤʤǡƱϥåͤƤ뤳Ȥ͡ʥꥸˤ뤤ϥΥ˥Ȥ˳ǼƤ쥳ɡʥǡˤۡ쥳夫Ǽ줿ʾͤΤ˳ǼǤʤ˥쥳ɡʥǡˤΥ˥쥳Ȥ

褹륢ץ2̤ꤢ롣

  1. ϥåؿ¦˾ͺʾͤ򸺤餹Υץˡ
    • ñmodǹͤƤޤȴñ˾ͤƤޤ
    • Źо줹ϥåؿϤͺCRCollision ResistanceˤɬפǤ롣
  2. ͤäȤ˥ǡǼΤ餷˹פʾͤȤ褹륢ץˡ
    • ץ󥢥ɥ쥹ˡ
    • ˡ

ԤΥץȤơSHA256ʤɤȤФȤꤢʳǤϾͤβǽϾʤŹŪ˰ʥϥåؿ򤽤Τޤ޻Ȥȥϥåͤ뤿λ֤äƤޤ⤷ʤ
ԤΥץϡԥ塼ʳؤˤƤǤˤĤˡƤƤ롣㤨Хץ󥢥ɥ쥹ˡˡʤɤ롣

ץ󥢥ɥ쥹ˡ

Ĥޤǥϥåͤ1äƤΤץ󥢥ɥ쥹ˡǤ롣

ƥϥåǼѤߤʤС˺ƥϥå夷Ƥơƥϥå夷礭Ķʤ顢ƬH(1)롣ʾΤȤޤȤȺƥϥåؿϼΤ褦ˤʤ롣

  • ֥ϥå͡礭פΤȤ
    • ƥϥåؿϥåؿ+1
  • ֥ϥå͡礭פΤȤ
    • ƥϥåؿ1

ץ󥢥ɥ쥹ˡǤϡƤȤ˥Υ˥쥳ɤǼΤǡϥåɽˤ˳ǡ¸ߤƤƤ⡢ϥåͤΰ֤˥ǡȤϸ¤ʤϥåͤΰ֤ˤǡפʤϡƥϥåͤᡢӤƤʤФʤʤϥåͤΰ֤鲼ظƤֲˤä־夫Ĵ٤ƤȤˤʤ롣ϥåɽǤˤ٤ƳǼѤߤξϥϥåɽΥǡ򤹤٤Ĵ٤Ƥʤȡǡ¸ߤʤȤ狼롣

̾ΰˤ-1򥻥åȤƤ뤳Ȥǡ٤ƤΥǡåʤƤǡʤȤ狼뤳Ȥ롣

㡧329H(1)ޤĴ٤Сϥåɽ¸ߤʤȤ狼롣

ϥåɽ礭Υ˥बäȯʤϥåؿʤСץ󥢥ɥ쥹ˡǤ褤Υ˥ȯͽ¬ǤȤϡ¾ˡѤۤ褤

ˡ

餫᥷Υ˥쥳ɤΰͽ󤷤Ƥإݥ󥿤ĤʤΤˡǤ롣ۥƥ㤨ʤСС֥å󥰤ȯͽ¬ǤȤͽ󤵤˰ޤǶΤޤޥפƤСΤȤˤȤȤ櫓Ǥ롣Υץϼºݤ˥ۥƥαѤˤƤ褯ȤƤ롣

㡧ϥåؿǡmod 5Ƿ׻Ƥ1û褦ʴؿȤ롣ޤH(1)H(5)ޤǤۡ쥳ɤΰ衢H(6)H(10)ޤǤ򥷥Υ˥쥳ɤΰˤ롣

P(1)6ʤΤǡH(6)˥Υ˥쥳ɤǼƤ뤳Ȥ̣롣ݥ󥿤0ΤȤϡΥ˥쥳ɤʤȤ̣롣

ˡ400ǼȤȤͤƤߤ褦ϥåͤ1H(1)ϤǤ˳ǼѤߤʤΤǡƤH(7)˳Ǽ롣ơH(1)ݥ󥿤򤿤ɤäơP(6)Υݥ󥿤7ˤΤǤ롣

ΥץνפʥݥȤϡϥåɽ˥ݥ󥿤ĤȤǤ롣嵭ǤϥݥѤPѤƤ뤬2ˤƼ륿פ⤢롣

ϥåˡħ

  • å
    • Υ˥बȯʤ硢Ǥο˴طʤϥåؿη׻1¹Ԥ롣
  • ǥå

ϥåˡή

Ƶ򼡤Τ褦롣

  • iǤֹ
  • nǿ
  • Xõǡ

Ǥñʥϥåˡ

ץ󥢥ɥ쥹ˡ

ϥåͤΥǡȰפʤȤƥϥåͤɬפꡢήޤϥ롼׹¤ˤʤ롣롼פνλϼ̤Ǥ롣

  1. õǡĤäȤ
  2. ƥϥåͤǤ-1ˤǤäȤ
  3. ٤ƤΥǡӤƤõǡȰפʤȤ

λ郎ʣʤΤǡ˼ήޤǤϡflgȤѿѤ롣ήޤέϡ嵭ֹб롣

ˡ

nP(n)פǡݥ󥿤ФƤΤݥȤǤ롣

ϥåˡη׻

ϥåˡˤõǤϡΥ˥बȯʤ硢Ǥο˴طʤϥåؿη׻1¹Ԥ롣Ĥޤꡢϥåˡη׻̤ΥO~\(~1~\)Ǥ롣

¸

JavaȤäϥåˡμ¸

ϥåˡˤäơñϿJavaץäƤߤ롣Τ褦ʵǽ롣

  • ޥɥ饤󤫤ǿꤹ롣
  • ñ򥭡ϤơϥåˡϿ롣
    • ͤä顢ϿԤ鷺˥åɽ롣
  • Ͽ顢ñ򥭡ϤơϥåˡǸ롣

ñϿȸϥ饹᥽åɤˤ롣ϿInsert᥽åɡSearch᥽åɤȤ롣

Insert᥽åɤϡmain᥽åɤϿñ롣

  • 르ꥺ: Insert
  • Input: stringñ
  • Output: 1 or 01Ԥ0
  1
  2
  3
  4
  5
  6
hHash(string)
if length(HashTable[h])0 then
    return 0
else
    HashTable(h)string
    return 1

Ǥϥ르ꥺInsert(string)ˤĤƲ⤹롣
1ܤstringΥϥåͤơhƤ롣
2ܤܤΥϥå쥳ɤʸĹ0ǤʤʤС0֤ǤʤʤСϤǤstringhܤΥ쥳ɤɲäơ1֤

Search᥽åɤϡmain᥽åɤ鸡ñ롣

  • 르ꥺ: Search
  • Input: stringñ
  • Output: hֹ档⤷Ԥ-1
  1
  2
  3
  4
hHash(string)
if HashTable[h]string then
    return h
return -1

Ǥϥ르ꥺSearch(string)ˤĤƲ⤹롣
1ܤstringΥϥåͤơhƤ롣
2ܤhܤΥϥå쥳ɤʸ󤬰פƤ뤫Ĵ٤롣JavaǤString饹equal᥽åɤȤäơif(HashTable[h].equals(s) == true){}פȤФ褤פƤʤСֹh֤

main᥽åɤǤϡ2ĤΥ᥽åɤȤäΤ褦ʽˤʤ롣

  1. ϥåơ֥ǿ򥳥ޥɥ饤󤫤롣
  2. ϥåơ֥롣
  3. LoopϽλޤǷ֤
    1. ñ򥭡Ϥ롣
    2. ϥåˡˤäñϿ롣Insert᥽åɤƤӽФ
    3. IfϿ˼Ԥ顢åɽ롣
  4. ¸줿ñɽ롣
  5. LoopλޤǷ֤
    1. ñϤ롣
    2. ϥåˡˤäñõSearch᥽åɤƤӽФ
    3. IfĤäñΰ֤ɽ롣Else顼åɽ롣

Ǹ˹ͤʤФʤʤΤȤơϥåؿ롣ŹǻȤϥåؿǤϤʤǤϼΤ褦ñʻȤߤδؿѤ뤳Ȥˤ롣

  • 르ꥺ: Hash
  • Input: stringñ
  • Output: hʥϥå͡
  1
  2
  3
  4
  5
h=0
for i=0,,length(string) do
    hh+(stringiܤʸ)
hh % (ǿ)
return h

ϥåˡ¹ԤJavaΥץϼ̤ǤHashTest.javaˡ

Everything is expanded.Everything is shortened.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
 
 
 
 
 
 
-
|
|
|
|
|
|
|
|
-
|
|
-
|
!
|
|
|
|
!
|
|
|
|
-
|
-
|
!
|
|
!
|
|
|
|
-
|
-
|
!
|
!
|
|
-
|
-
|
|
-
|
-
|
|
!
|
|
|
-
|
!
|
|
|
-
-
|
|
|
|
-
|
!
|
|
-
|
|
|
|
!
-
|
|
!
!
|
|
|
-
|
|
!
|
|
|
-
|
-
|
|
|
|
-
|
!
|
|
|
|
-
|
|
-
|
|
!
-
|
|
!
!
!
!
 
/*
 * HashTestϥåˡˤǡ¸
 * ϡǿʰˡ¸ñϡˡñϡ
 * ϡ
 */
import java.io.*;
 
public class HashTest {
    //饹ѿ
    static String[] HashTable;    //ϥåơ֥
    static int TableMax;        //ǿ
    
    //Hashϥåͤ
    //sñ
    //maxǿ
    //͡ϥå
    static int Hash(String s){
        //ʸκǸޤǡʸɤ­
        int h=0;
        for(int i=0;i<s.length();i++){
            h += s.charAt(i);    //iܤʸɤ­
        }
        System.out.println("Hash:"+h);    //ʸɤ­̤ɽ
        h = h % TableMax;    //ǿdzä;
        System.out.println("->"+h);    //ϥåͤɽ
        return h;
    }
    
    //Insertϥåˡñ¸
    //sñ
    //͡trueͤȯfalse
    static boolean Insert(String s){
        int h=Hash(s);
        if(HashTable[h].length() != 0){
            return false;
        }
        HashTable[h]=s;
        return true;
    }
    
    //Searchϥåˡñ򸡺
    //sñ
    //͡ʤֹʼԤʤ-1
    static int Search(String s){
        int h=Hash(s);
        if(HashTable[h].equals(s) == true){
            return h;
        }
        return -1;
    }
 
    //main
    public static void main(String[] args) {
        //ǿȤƥޥɥ饤󤫤
        if(args.length != 1){
            System.out.println("HashTest <m> m:ǿ");
            return;
        }try{
            TableMax=Integer.parseInt(args[0]);
        }catch(NumberFormatException e){
            System.out.println("˻ꤷƤ");
            return;
        }
        
        //
        HashTable = new String[TableMax];
        for(int i=0;i < HashTable.length;i++){
            HashTable[i]="";
        }
        
        //ñϤ¸
        BufferedReader rd=new BufferedReader(new InputStreamReader(System.in));
        for(int i=0;i < TableMax;i++){
            try{
                System.out.println(i+": ñʽλ꥿ˡ");
                String ln=rd.readLine();
                
                //Ϥʤнλ
                if(ln.length() == 0){
                    break;
                }
                
                //ϥåˡñ¸
                if(Insert(ln) == false){
                    System.out.println("ͤȯ");
                    //ͤ¸ʤ
                    i--;
                    continue;
                }
            }catch(IOException e){
                System.out.println("ϥ顼");
                return;
            }
        }
        
        //¸줿ñɽ
        System.out.println();
        for(int k=0;k < HashTable.length;k++){
            if(HashTable[k].length() > 0)
                System.out.println(k+":"+HashTable[k]+"\t");
        }
        System.out.println();
        
        //
        while(true){
            //õñϤ
            try{
                System.out.println("õñʽλ꥿ˡ");
                String wd=rd.readLine();
                
                //꥿ʤ齪λ
                if(wd.length() == 0){
                    break;
                }
                
                //ñõ
                int n=Search(wd);
                
                if(n >= 0){
                    //Ĥä餽ΰ֤ɽ
                    System.out.println(wd+""+n+"ܤǤ롣");
                }else{
                    //ĤʤХåɽ롣
                    System.out.println(wd+"ϸĤʤ");
                }
            }catch(IOException e){
                System.out.println("ϥ顼Ǥ롣");
                return;
            }
        }
    }
}

Υץ¹ԤȡΤ褦ˤʤ롣ϥåơ֥ǿǿˤȳڤ뤳ȤʤʤΤǡϥåͤʬ褦ˤʤ롣äơǤϰȤ11ꤷ

> java HashTest 11	ο11ˤ
0: ñʽλ꥿ˡ	Ͽ⡼ɤϤޤ롣
test	testHashTableϿ롣
Hash:448	testΥϥåͤ448Ǥ롣
->8	448 (mod 11)8פȷ׻ǤΤǡ8testϿ
1: ñʽλ꥿ˡ
hack
Hash:407
->0
2: ñʽλ꥿ˡ
crack
Hash:516
->10
3: ñʽλ꥿ˡ
krack
Hash:524
->7
4: ñʽλ꥿ˡ
virus
Hash:569
->8
ͤȯ	virus8ϤǤñ줬ʾͤˡ
4: ñʽλ꥿ˡ
network
Hash:778
->8
ͤȯ	network8ϤǤñ줬ʾͤˡ
4: ñʽλ꥿ˡ	꥿ϤơϿ⡼ɤϽλ


0:hack		HashTableɽơ⡼ɤ˰ܹԤ롣
7:krack
8:test
10:crack

õñʽλ꥿ˡ
hack
Hash:407
->0
hack0ܤǤ롣
õñʽλ꥿ˡ
crack
Hash:516
->10
crack10ܤǤ롣
õñʽλ꥿ˡ
network	networkHashTable¸ߤʤϿΤȤ˾ͤ顢ɲäʤä
Hash:778
->8
networkϸĤʤ
õñʽλ꥿ˡ	꥿Ϥơ⡼ɤϽλ

ͤ򤱤ǤѤʥץǤ륪ץ󥢥ɥ쥹ˡͤƤߤ롣᤿ϥåͤ1­ơǿdzä;ȤˡǤ롣ΰ֤Ǥͤ顢1­;롣Ƥ֤ĤޤǷ֤ΤǤ롣

ҤInsert르ꥺSearch르ꥺФ褤

  • 르ꥺ: Insert
  • Input: stringñ
  • Output: 1 or 01Ԥ0
  1
  2
  3
  4
  5
  6
  7
hHash(string)
for i=0,,(ǿ) do
    if length(HashTable(h))=0 then
        stringHashTable(h)
        return true;
    h(h+1)%(ǿ)
return false

嵭ץTestHash.javaˤˤƤϡ(ǿ)TableMax˳롣ޤHash᥽åɤѤ餺Τޤ޻ȤäƤ褤

  • 르ꥺ: Search
  • Input: stringñ
  • Output: hֹ档⤷Ԥ-1
  1
  2
  3
  4
  5
  6
hHash(string)
for i=0,,(ǿ) do
    if HashTable[h]string then
        return h
    h(h+1)%(ǿ)
return -1

ϥåˡѾ

  • ץߥ󥰸ѥˤơФƤñϿåˡϥåˡȤƤ롣

ޤȤ

Ƽõ르ꥺΥޤȤƤ

르ꥺ̾
ϥåˡO~\(~1~\)
õˡO~\(~n~\)
ХʥꥵO~\(~\log~n~\)

1ֿؿnпؿlog(n)ĿǤ롣

ʸ

  • ֵΡ
  • إեȥȯѼԡкʴԡˡƥȡ
  • Ķ޲miniܾ󵻽ѼԻʿ19ǯǡ
  • 1֤ʬܾ󵻽ѼԽ楼ߡڸԡۡ2006ս
  • ϤζܤȤƤξء
  • EclipseˤθؽJavaǤϤ륢르ꥺ