Bitcoin full node and query server
Mar 7, 2025
View in context in the libbitcoin Slack #general mirror.
evoskuil19:25
the hashmap head. the hash function for the point table is a std::hash combine of the tx.hash and the index. the hash of the tx.hash is the first 4 bytes.
35 replies · cguida, evoskuil · last Mar 07, 2025
C
cguida19:33
When you say "the first 4 bytes", do you mean the first 4 bytes of the txid (which i think you are calling tx.hash here)?
evoskuil19:35
For the tables that have a sha hash (or a point .... hash:index) as the natural key (search key), the hashmap's hash function doesn't do math on the sha hash, it just takes the low order bytes from the sha hash in the length it requires. all that is necessary for a hashmap hash function is evenness, and sha satisfies this, apart from high order bytes in header hashes.
evoskuil19:36
We found that this is by far the most efficient and evenly distributed hash function, it's basically perfect, or at least ideal (normal distribution).
(edited)👍 1
evoskuil19:37
For hashmaps that key off of the surrogate key (store id) of another table, the hash function is just the key value, since keys are sequential and therefore perfectly evenly distributed. even better than the sha normal distribution.
👍 1
evoskuil19:38
These values are then shifted in the header domain, which is determined by desired load factor.
C
cguida19:38
ok so for a point that looks like
aabbccdd.......:0, in the point table the hashmap key is aabbccdd?evoskuil19:39
These are stored in link-sized values (3, 4, 5, 6 bytes currently) in the head buckets and table rows. The head provides the list (actually stack) top and the links provide the reset.
👍 1
C
cguida19:39
sorry i'm not that familiar with hashmap internals, i just stick in a hash and out comes a value haha
evoskuil19:39
The link value sizes are determined by the size of the table (so they don't overflow the restricted integer domains).
evoskuil19:40
The load fact (bucket count) is configured to balance average search conflicts against header size.
evoskuil19:41
The key for a point is the combination of the
aabbccdd and the 0 . This requires a mathematical operation called hash combination.evoskuil19:43
The ideal hash function is no function, just truncate the natural key and shift into bucket domain.
👍 1
evoskuil19:44
namespace std
{
template<>
struct hash<bc::system::chain::point>
{
size_t operator()(const bc::system::chain::point& value) const NOEXCEPT
{
return bc::system::hash_combine(value.index(),
bc::system::unique_hash(value.hash()));
}
};
template<>
struct hash<bc::system::chain::point_cref>
{
std::size_t operator()(
const bc::system::chain::point_cref& value) const NOEXCEPT
{
return std::hash<bc::system::chain::point>{}(value.get());
}
};evoskuil19:44
// Combine hash values, such as a pair of djb2_hash outputs.
INLINE constexpr size_t hash_combine(size_t left, size_t right) NOEXCEPT
{
return left ^ shift_left(right, one);
}evoskuil19:45
template <size_t Size>
INLINE constexpr size_t unique_hash(const data_array<Size>& key) NOEXCEPT
{
constexpr auto size = std::min(Size, sizeof(size_t));
// This optimization breaks data portability (by endianness).
// Could be modified to use an endian conversion vs. simple copy.
size_t value{};
std::copy_n(key.begin(), size, system::byte_cast(value).begin());
return value;
}evoskuil19:46
This is a typical good hash function. It was dramatically less efficient than our "unique hash" for sha values.
// Objectives: deterministic, uniform distribution, efficient computation.
INLINE constexpr size_t djb2_hash(const data_slice& data) NOEXCEPT
{
// Nothing special here except that it tested well against collisions.
auto hash = 5381_size;
// Efficient sum of ((hash * 33) + byte) for all bytes.
for (const auto byte: data)
hash = (shift_left(hash, 5_size) + hash) + byte;
return hash;
}
C
cguida20:01
does hash_combine produce adjacent hashes by numerical order, for different outputs of the same tx?
evoskuil20:09
Ideally all hashes are evenly distributed, but "completely different" is a bit hopeful.
evoskuil20:12
If you are thinking that clustering by tx.hash would be beneficial, that's not the case. It would result in long conflict chains with no benefit. Outputs of the same tx are not consistently spent by the same tx. But in any case all outputs of a tx are in fact clustered into contiguous rows in the point table.
(edited)👍 1
C
cguida20:18
Okay that's what I was asking. It does sound like if you xor the vout to the left-shifted txid, then you would end up with contiguous rows by txid
evoskuil21:04
All table bodies are append only, and rows are allocated in a batch for a given tx. So they are inherently contiguous. Even if the allocation was not contiguous due to individual allocation (as previously) data locality wouldn't be materially affected, and that's the only real cost (paging).
(edited)