HashMap length greater than capacity.

[oampo]

With HashMaps of capacity of 58 or greater it is possible to have a length which is larger than the reported capacity. Here's a test which demonstrates the problem:

#![feature(core)]
use std::collections::HashMap;

fn find_broken(size: usize) {
    let mut a: HashMap<usize, usize> = HashMap::with_capacity(size);

    // Fill the hashmap up to its capacity
    for i in range(0, a.capacity()) {
        a.insert(i, i);
    }

    // Add one more element.  Should reallocate in theory.
    let cap = a.capacity();
    a.insert(cap, cap);

    if a.len() > a.capacity() {
        // OMGWTF?!?!?
        println!("{} {} {}", size, a.len(), a.capacity());
    }
}

fn main() {
    for i in range(0, 255) {
        find_broken(i);
    }
}

rustc version:

rustc 1.0.0-nightly (4be79d6ac 2015-01-23 16:08:14 +0000)
binary: rustc
commit-hash: 4be79d6acde9eed3a9b5281a46f385bcb4ce736c
commit-date: 2015-01-23 16:08:14 +0000
host: x86_64-unknown-linux-gnu
release: 1.0.0-nightly

[nagisa]

cc @gankro

[Gankra]

This well defined behaviour by the specification of capacity. It is a lower-bound on how many elements which will fit.

[Gankra]

Hashmap is the only collection with these semantics as a consequence of integer division.

[oampo]

Ah, okay - that makes sense. Just looked a little odd - I was worried that it might mean a more serious underlying problem. Thanks folks!