[ Pobierz całość w formacie PDF ]
.6 Type declaration for separate chaining hash tableusually kept, and this data member would be incremented in the event of a match).If theelement turns out to be new, it can be inserted at the front of the list, since it is convenientand also because frequently it happens that recently inserted elements are the most likelyto be accessed in the near future.The class interface for a separate chaining implementation is shown in Figure 5.6.Thehash table stores an array of linked lists, which are allocated in the constructor.The class interface illustrates a syntax point: Prior to C++11, in the declaration oftheLists, a space was required between the two>s; since>>is a C++ token, and because itis longer than>,>>would be recognized as the token.In C++11, this is no longer the case.Just as the binary search tree works only for objects that areComparable, the hash tablesin this chapter work only for objects that provide a hash function and equality operators(operator==oroperator!=, or possibly both).Instead of requiring hash functions that take both the object and the table size asparameters, we have our hash functions take only the object as the parameter and returnan appropriate integral type.The standard mechanism for doing this uses function objects,and the protocol for hash tables was introduced in C++11.Specifically, in C++11, hashfunctions can be expressed by the function object template:templateclass hash{public:size_t operator() ( const Key & k ) const;}; 198 Chapter 5 HashingDefault implementations of this template are provided for standard types such asintandstring; thus, the hash function described in Figure 5.4 could be implemented astemplateclass hash{public:size_t operator()( const string & key ){size_t hashVal = 0;for( char ch : key )hashVal = 37 * hashVal + ch;return hashVal;}};The typesize_tis an unsigned integral type that represents the size of an object;therefore, it is guaranteed to be able to store an array index.A class that implements ahash table algorithm can then use calls to the generic hash function object to generate anintegral typesize_tand then scale the result into a suitable array index.In our hash tables,this is manifested in private member functionmyhash, shown in Figure 5.7.Figure 5.8 illustrates an Employee class that can be stored in the generic hashtable, using thenamemember as the key.TheEmployeeclass implements theHashedObjrequirements by providing equality operators and a hash function object.The code to implementmakeEmpty,contains, andremoveis shown in Figure 5.9.Next comes the insertion routine.If the item to be inserted is already present, then wedo nothing; otherwise, we place it in the list (see Fig.5.10).The element can be placedanywhere in the list; usingpush_backis most convenient in our case.whichListis a referencevariable; see Section 1.5.2 for a discussion of this use of reference variables.Any scheme could be used besides linked lists to resolve the collisions; a binary searchtree or even another hash table would work, but we expect that if the table is large and thehash function is good, all the lists should be short, so basic separate chaining makes noattempt to try anything complicated.We define the load factor, », of a hash table to be the ratio of the number of elementsin the hash table to the table size.In the example above, » = 1.The average length of alist is ».The effort required to perform a search is the constant time required to evaluatethe hash function plus the time to traverse the list.In an unsuccessful search, the number1 size_t myhash( const HashedObj & x ) const2 {3 static hash hf;4 return hf( x ) % theLists.size( );5 }Figure 5.7 myHashmember function for hash tables 5.3 Separate Chaining 1991 // Example of an Employee class2 class Employee3 {4 public:5 const string & getName( ) const6 { return name; }78 bool operator==( const Employee & rhs ) const9 { return getName( ) == rhs [ Pobierz caÅ‚ość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl centka.pev.pl
.6 Type declaration for separate chaining hash tableusually kept, and this data member would be incremented in the event of a match).If theelement turns out to be new, it can be inserted at the front of the list, since it is convenientand also because frequently it happens that recently inserted elements are the most likelyto be accessed in the near future.The class interface for a separate chaining implementation is shown in Figure 5.6.Thehash table stores an array of linked lists, which are allocated in the constructor.The class interface illustrates a syntax point: Prior to C++11, in the declaration oftheLists, a space was required between the two>s; since>>is a C++ token, and because itis longer than>,>>would be recognized as the token.In C++11, this is no longer the case.Just as the binary search tree works only for objects that areComparable, the hash tablesin this chapter work only for objects that provide a hash function and equality operators(operator==oroperator!=, or possibly both).Instead of requiring hash functions that take both the object and the table size asparameters, we have our hash functions take only the object as the parameter and returnan appropriate integral type.The standard mechanism for doing this uses function objects,and the protocol for hash tables was introduced in C++11.Specifically, in C++11, hashfunctions can be expressed by the function object template:templateclass hash{public:size_t operator() ( const Key & k ) const;}; 198 Chapter 5 HashingDefault implementations of this template are provided for standard types such asintandstring; thus, the hash function described in Figure 5.4 could be implemented astemplateclass hash{public:size_t operator()( const string & key ){size_t hashVal = 0;for( char ch : key )hashVal = 37 * hashVal + ch;return hashVal;}};The typesize_tis an unsigned integral type that represents the size of an object;therefore, it is guaranteed to be able to store an array index.A class that implements ahash table algorithm can then use calls to the generic hash function object to generate anintegral typesize_tand then scale the result into a suitable array index.In our hash tables,this is manifested in private member functionmyhash, shown in Figure 5.7.Figure 5.8 illustrates an Employee class that can be stored in the generic hashtable, using thenamemember as the key.TheEmployeeclass implements theHashedObjrequirements by providing equality operators and a hash function object.The code to implementmakeEmpty,contains, andremoveis shown in Figure 5.9.Next comes the insertion routine.If the item to be inserted is already present, then wedo nothing; otherwise, we place it in the list (see Fig.5.10).The element can be placedanywhere in the list; usingpush_backis most convenient in our case.whichListis a referencevariable; see Section 1.5.2 for a discussion of this use of reference variables.Any scheme could be used besides linked lists to resolve the collisions; a binary searchtree or even another hash table would work, but we expect that if the table is large and thehash function is good, all the lists should be short, so basic separate chaining makes noattempt to try anything complicated.We define the load factor, », of a hash table to be the ratio of the number of elementsin the hash table to the table size.In the example above, » = 1.The average length of alist is ».The effort required to perform a search is the constant time required to evaluatethe hash function plus the time to traverse the list.In an unsuccessful search, the number1 size_t myhash( const HashedObj & x ) const2 {3 static hash hf;4 return hf( x ) % theLists.size( );5 }Figure 5.7 myHashmember function for hash tables 5.3 Separate Chaining 1991 // Example of an Employee class2 class Employee3 {4 public:5 const string & getName( ) const6 { return name; }78 bool operator==( const Employee & rhs ) const9 { return getName( ) == rhs [ Pobierz caÅ‚ość w formacie PDF ]