3 // Copyright (C) 2005-2023 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
65 typedef size_t size_type
;
67 simple_string_ranged_hash_fn() : m_container_size(0) { }
69 // Called to notify that the size has changed.
71 notify_resized(size_t size
)
72 { m_container_size
= size
; }
74 // Called for hashing a string into a size_t in a given range.
76 operator()(const string
& r_string
)
79 * This (simplified) hash algorithm decides that if there are
80 * fewer than 100 strings in the container it will hash
81 * a string by summing its characters; otherwise, it will
82 * perform a more complicated operation in order to produce
83 * hash values with fewer collisions.
85 string::const_iterator it
= r_string
.begin();
87 if (m_container_size
< 100)
89 // For this size, perform an accumulate type of operation.
90 while (it
!= r_string
.end())
91 hash
+= static_cast<size_t>(*it
++);
95 // For this size, perform a different operation.
96 while (it
!= r_string
.end())
98 hash
+= static_cast<size_t>(*it
++);
103 // The function must, by whatever means, return a size in the
104 // range 0 to m_container_size.
105 return hash
% m_container_size
;
110 swap(simple_string_ranged_hash_fn
& other
)
112 std::swap(m_container_size
, other
.m_container_size
);
116 // Records the size of the container object.
117 size_t m_container_size
;
123 // A collision-chaining hash table storing strings.
130 simple_string_ranged_hash_fn
>
133 // Note that in the above, the library determines a resize policy
134 // appropriate for modulo-based range hashing.
137 // Use the table normally.
141 assert(h
.size() == 2);
143 assert(h
.find("Hello, ") != h
.end());
144 assert(h
.find("world") != h
.end());
146 assert(h
.find("Goodbye, oh cruel world!") == h
.end());