Tpetra_Details_Hash.cpp

// @HEADER
// *****************************************************************************
//          Tpetra: Templated Linear Algebra Services Package
//
// Copyright 2008 NTESS and the Tpetra contributors.
// SPDX-License-Identifier: BSD-3-Clause
// *****************************************************************************
// @HEADER

#include "Tpetra_Details_Hash.hpp"

namespace Tpetra {
namespace Details {
namespace Impl {

int getRecommendedSizeInt(const int size) {
  // A large list of prime numbers.
  // Based on a recommendation by Andres Valloud in hash forums.
  //  There are only enough primes here so that between any number N and 2*N,
  //  there will be at least about 8 to choose from (except the first 10).
  //  This is a balance between a small list of primes, and getting a
  //  collection size that doesn't waste too much space.  In addition,
  //  the primes in this table were chosen so that they do not divide
  //  256^k +- a, for 1<=k<=8, and -32<=a<=32.  This is so that
  //  using them as a modulo will not have a tendency to just throw away
  //  the most significant bits of the object's hash.  The primes (except the
  //  first ten) or not close to any power of two to avoid aliasing
  //  between hash functions based on bit manipulation and the moduli.
  int primes[] = {
      3, 7, 13, 23, 53, 97, 193, 389, 769, 1543,
      2237, 2423, 2617, 2797, 2999, 3167, 3359, 3539,
      3727, 3911, 4441, 4787, 5119, 5471, 5801, 6143, 6521, 6827, 7177, 7517, 7853, 8887, 9587, 10243, 10937, 11617, 12289, 12967, 13649, 14341, 15013, 15727, 17749, 19121, 20479, 21859, 23209, 24593, 25939, 27329, 28669, 30047, 31469, 35507, 38231, 40961, 43711, 46439, 49157, 51893, 54617, 57347, 60077, 62801, 70583, 75619, 80669, 85703, 90749, 95783, 100823, 105871, 110909, 115963, 120997, 126031, 141157, 151237, 161323, 171401, 181499, 191579, 201653, 211741, 221813, 231893, 241979, 252079, 282311, 302483, 322649, 342803, 362969, 383143, 403301, 423457, 443629, 463787, 483953, 504121, 564617, 604949, 645313, 685609, 725939, 766273, 806609, 846931, 887261, 927587, 967919, 1008239, 1123477, 1198397, 1273289, 1348177, 1423067, 1497983, 1572869, 1647761, 1722667, 1797581, 1872461, 1947359, 2022253, 2246953, 2396759, 2546543, 2696363, 2846161, 2995973, 3145739, 3295541, 3445357, 3595117, 3744941, 3894707, 4044503, 4493921, 4793501, 5093089, 5392679, 5692279, 5991883, 6291469, 6591059, 6890641, 7190243, 7489829, 7789447, 8089033, 8987807, 9586981, 10186177, 10785371, 11384539, 11983729, 12582917, 13182109, 13781291, 14380469, 14979667, 15578861, 16178053, 17895707, 19014187, 20132683, 21251141, 22369661, 23488103, 24606583, 25725083, 26843549, 27962027, 29080529, 30198989, 31317469, 32435981, 35791397, 38028379, 40265327, 42502283, 44739259, 46976221, 49213237, 51450131, 53687099, 55924061, 58161041, 60397993, 62634959, 64871921, 71582857, 76056727, 80530643, 85004567, 89478503, 93952427, 98426347, 102900263, 107374217, 111848111, 116322053, 120795971, 125269877, 129743807, 143165587, 152113427, 161061283, 170009141, 178956983, 187904819, 196852693, 205800547, 214748383, 223696237, 232644089, 241591943, 250539763, 259487603, 268435399};

  int hsize = primes[220];
  for (int i = 0; i < 221; ++i) {
    if (size <= primes[i]) {
      hsize = primes[i];
      break;
    }
  }
  return hsize;
}

}  // namespace Impl
}  // namespace Details
}  // namespace Tpetra