Алгоритмы и структуры данных осень 2013 лекция 7

  • Published on
    15-Jun-2015

  • View
    637

  • Download
    0

Embed Size (px)

Transcript

  • 1. 7. -. . .

2. - -. -. . . . . - .2 3. , : , . i, i i, . .. . . . 3 4. : 1. -, . 2. , .. .4 5. - . - ( ) (). - .. - H X Y , = .5 6. - , = K, - M k: 0 < . ! - : 1. . 2. . , - .HASH = , .6 7. - -. h(k) = [ [] k] = k % 1000. - , . : 000, 500, 999, 998, 990, 900.7 8. - . = mod .M : [0, .. , M1]. M. M , . = 28 1, .. - . M , . 8 9. - . . K 0 , 1 , , 1 . = 0 + 1 + + 1 1 . = 0 + 1 + + . - : = mod = 0 + 1 + + = 0 , 1 , , 1 .11= , p . CRC p = 2. 9 10. - ( -). = , {} , [] , A , 0 < < 1, M : [0, .. , M1]. A , : 51 1 = = = 0.6180339887 2 A . 10 11. - ( -). - = . M . = 2 , 32. A 2654435769 = 32 = . = 2654435769. 32 22 = 2 = 2 01 232 +00 232, =232= 2 1 232 +0 232= 2 0232= 01 = 0 . . 11 12. - s 0 , 1 , , 1 . 1. 1 = 0 + 1 + 2 2 + + 1 1 mod . 2. 2 = 0 1 + 1 2 + + 2 + 1 mod . M : [0, .. , M1]. M . a. , mod , 0 < . , a M . .12 13. - . 1) a M , mod , 0 < {0, , 1}. 2) a M , mod , 0 < = {0, , 1}. . 1) a M . a M d. = , = . s M d: = + , = = . 2) . mod , 0 < M . i j, (mod ), < < . , = . , , .. . 0 < < . . 13 14. - 2 , : 2 =0 + 1 + 2 + + 2 + 1 .1 , . c- , . 2 .14 15. - // - . int Hash( const char* str, int m ) { int hash = 0; for( ; *str != 0; ++str ) hash = ( hash * a + *str ) % m; return hash; }15 16. - . : 1. CRC , Cyclic redundancy check. . . CRC1, CRC8, CRC32. 2. MD1, MD2, MD3, MD4, MD5, MD6 . MD5 128- . 3. SHA-1, SHA-2 256, 512- . , .. . 16 17. - . - , . . : , , . - M, N.. , ( -), - (load factor). = . , . 17 18. - . - 365 23- 50 % ( ).- . : 1. . 2. . 18 19. -. . (). , .19 20. -. . . 1. - h.2. A[h] .3. ( ). , . : O(1). , O(1), O(N). 20 21. -. . . 1. - h.2. A[h] .3. . : O(1). O(N).21 22. -. . . 1. - h.2. A[h] .3. . : O(1). O(N).22 23. -. . . . , ( ) -, (1 + ), . . . 1 + , i- . , - , . 1 , = =1+ = =01 1 1 + = 1=0+ 1 + = 23 24. -. . . . , A , , O(1 + ), .24 25. -. . // -. template int Hash( T& data ); // -. template struct CHashTableNode { T Data; CHashTableNode* Next; }; // -. template class CHashTable { public: CHashTable( int initialSize ); bool Has( T& key ) const; void Add( T& key ); bool Delete( T& key ); private: vector*> table; }; 25 26. -. . . , NIL. , .26 27. -. . . 1. - h.2. , A[h], , . 3. . .2 . .27 28. -. . . , ( 0). 0, 1, , 1 0, 1, , 1 ., k , 0 , , 1 , , , 1 0,1, , 1 , .28 29. -. . // -. void CHashTable::Insert( T& k ) { for( int i = 0; i < tableSize; ++i ) { int j = h( k, i ); if( IsNil( table[j] ) ) { table[j] = k; return j; } } throw CHashTableException( Overflow ); }29 30. -. . . , . , , , .30 31. -. . . . i NIL. ( ) , . . . Deleted. . Deleted, . Deleted.31 32. -. . . , k , 0 , , 1 , , , 1 - 0,1, , 1 . h(k, i):1. . 2. . 3. .32 33. -. . . , = + mod . . 1 , = 2 , , 1 , + = 2 , + r. .33 34. -. . . , = + 1 + 2 2 mod . , 0, .. , M1. 1 2 . . 1 , 0 = 2 , 0 , 1 , = 2 , i. , .34 35. -. . . , = 1 + 2 mod ., 0, .. , M1. 2 M. M , 2 . M , 2 M. = 2 . 35 36. -. . - . . - = < 1 1 . 1 . , : O(1). O(N). 1 . 136 37. -. . . + . + , . . - . 1. 1 , N. . 37 38. -. . 1, 1. : 1 + , 1/(1 ) . . . - .38 39. -. . 1. . 2 , . , 2 .2. . . -, 0 1.39 40. -. ? - . -, : , 1. -, :, .40 41. - . . . .. .. < .. .O(log n)O(log n)O(1)O(1)O(n)O(log n)O(log n)O(1)O(1)O(n)O(log n)O(log n)O(1)O(1)O(n)41 42. ? !

Recommended

View more >