int32_t big_array[2^32] = {0};
    
    /* returns the key */
    int64_t write(int_32 value)
    {
        big_array[value]++;
        return big_array[value] << 32 & value;
    }
    
    /* returns the value */
    int32_t read(int64_t key)
    {
        return (int32_t) key;
    }

    /* all indexes between 1 and the return value are valid higher half values 
    for the key. The lower half is the value itself. */
    int32_t seek(int32_t value)
    {
        return big_array[value];
    }

access: O(1)

seek: O(1)

Problem solved!

:)

edit: I'm missing the "Use less memory than an array in all circumstances" requirement, but hey, you talk about "billion of records" in your post.