3 // Copyright (C) 2005-2013 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING3. If not see
18 // <http://www.gnu.org/licenses/>.
21 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
23 // Permission to use, copy, modify, sell, and distribute this software
24 // is hereby granted without fee, provided that the above copyright
25 // notice appears in all copies, and that both that copyright notice
26 // and this permission notice appear in supporting documentation. None
27 // of the above authors, nor IBM Haifa Research Laboratories, make any
28 // representation about the suitability of this software for any
29 // purpose. It is provided "as is" without express or implied
33 * @file ranged_hash_example.cpp
34 * A basic example showing how to write a ranged-hash functor.
38 * In some cases it is beneficial to write a hash function which determines
39 * hash values based on the size of the container object.
40 * The example shows an example of a string-hashing function which
41 * uses a fast method for hashing strings when the number of strings
42 * in the container object is small, and a slower but more careful method
43 * for hashing strings when the number of strings in the container object
50 #include <ext/pb_ds/assoc_container.hpp>
51 #include <ext/pb_ds/hash_policy.hpp>
54 using namespace __gnu_pbds
;
57 * A (somewhat simplistic) ranged-hash function for strings.
58 * It uses the size of the container object to determine
59 * the hashing method. For smaller sizes it uses a simple hash function;
60 * for larger sizes it uses a more complicated hash function.
62 class simple_string_ranged_hash_fn
63 : public unary_function
<string
, size_t>
66 typedef size_t size_type
;
68 simple_string_ranged_hash_fn() : m_container_size(0) { }
70 // Called to notify that the size has changed.
72 notify_resized(size_t size
)
73 { m_container_size
= size
; }
75 // Called for hashing a string into a size_t in a given range.
77 operator()(const string
& r_string
)
80 * This (simplified) hash algorithm decides that if there are
81 * fewer than 100 strings in the container it will hash
82 * a string by summing its characters; otherwise, it will
83 * perform a more complicated operation in order to produce
84 * hash values with fewer collisions.
86 string::const_iterator it
= r_string
.begin();
88 if (m_container_size
< 100)
90 // For this size, perform an accumulate type of operation.
91 while (it
!= r_string
.end())
92 hash
+= static_cast<size_t>(*it
++);
96 // For this size, perform a different operation.
97 while (it
!= r_string
.end())
99 hash
+= static_cast<size_t>(*it
++);
104 // The function must, by whatever means, return a size in the
105 // range 0 to m_container_size.
106 return hash
% m_container_size
;
111 swap(simple_string_ranged_hash_fn
& other
)
113 std::swap(m_container_size
, other
.m_container_size
);
117 // Records the size of the container object.
118 size_t m_container_size
;
124 // A collision-chaining hash table storing strings.
131 simple_string_ranged_hash_fn
>
134 // Note that in the above, the library determines a resize policy
135 // appropriate for modulo-based range hashing.
138 // Use the table normally.
142 assert(h
.size() == 2);
144 assert(h
.find("Hello, ") != h
.end());
145 assert(h
.find("world") != h
.end());
147 assert(h
.find("Goodbye, oh cruel world!") == h
.end());