Is there a data structure that only stores hash codes and not the actual objects?2019 Community Moderator ElectionMemory size of Java 32-bit system BitSetsFastest way to determine if an integer's square root is an integerJava Class that implements Map and keeps insertion order?Why can't I retrieve an item from a HashSet without enumeration?Java tree data-structure?Gson: How to exclude specific fields from Serialization without annotationsHashcode and Equals for HashsetDirectly accessible data structure JavaJava HashSet vs Array PerformanceWhy hash set allows adding duplicate object?Why is (a*b != 0) faster than (a != 0 && b != 0) in Java?

What exactly is this small puffer fish doing and how did it manage to accomplish such a feat?

A sequence that has integer values for prime indexes only:

Existence of subset with given Hausdorff dimension

Science-fiction short story where space navy wanted hospital ships and settlers had guns mounted everywhere

Does Mathematica reuse previous computations?

Can I use USB data pins as power source

Define, (actually define) the "stability" and "energy" of a compound

Brexit - No Deal Rejection

Unexpected result from ArcLength

How difficult is it to simply disable/disengage the MCAS on Boeing 737 Max 8 & 9 Aircraft?

Why doesn't the EU now just force the UK to choose between referendum and no-deal?

How to deal with a cynical class?

Happy pi day, everyone!

Why Choose Less Effective Armour Types?

Professor being mistaken for a grad student

How to terminate ping <dest> &

Why is the President allowed to veto a cancellation of emergency powers?

Interplanetary conflict, some disease destroys the ability to understand or appreciate music

Most cost effective thermostat setting: consistent temperature vs. lowest temperature possible

A Cautionary Suggestion

Do the common programs (for example: "ls", "cat") in Linux and BSD come from the same source code?

How Could an Airship Be Repaired Mid-Flight

Why do Australian milk farmers need to protest supermarkets' milk price?

Does someone need to be connected to my network to sniff HTTP requests?



Is there a data structure that only stores hash codes and not the actual objects?



2019 Community Moderator ElectionMemory size of Java 32-bit system BitSetsFastest way to determine if an integer's square root is an integerJava Class that implements Map and keeps insertion order?Why can't I retrieve an item from a HashSet without enumeration?Java tree data-structure?Gson: How to exclude specific fields from Serialization without annotationsHashcode and Equals for HashsetDirectly accessible data structure JavaJava HashSet vs Array PerformanceWhy hash set allows adding duplicate object?Why is (a*b != 0) faster than (a != 0 && b != 0) in Java?










8















My use-case is that I'm looking for a data structure in Java that will let me see if an object with the same hash code is inside (by calling contains()), but I will never need to iterate through the elements or retrieve the actual objects. A HashSet is close, but from my understanding, it still contains references to the actual objects, and that would be a waste of memory since I won't ever need the contents of the actual objects. The best option I can think of is a HashSet of type Integer storing only the hash codes, but I'm wondering if there is a built-in data structure that would accomplish the same thing (and only accept one type as opposed to HashSet of type Integer which will accept the hash code of any object).










share|improve this question



















  • 4





    Is your hash function perfect? Or can you have multiple objects with the same hash value?

    – arshajii
    7 hours ago






  • 6





    what about hashing collisions?

    – Nathan Hughes台湾不在中国
    7 hours ago






  • 7





    The HashSet will contain a reference to your object, not a copy, so don't worry about space. A HashSet<Integer> would probably use up more space because it has references to integers.

    – Sweeper
    7 hours ago












  • I agree with @Sweeper, unless you have a real need for super-duper optimization. Also, your second idea with storing hashcodes as integer wouln't be more efficient as it would store the hash+the hash of the hash.

    – Joel
    7 hours ago











  • @Sweeper The HashSet uses internally a HashMap. The memory space is the same.

    – Octavian R.
    7 hours ago
















8















My use-case is that I'm looking for a data structure in Java that will let me see if an object with the same hash code is inside (by calling contains()), but I will never need to iterate through the elements or retrieve the actual objects. A HashSet is close, but from my understanding, it still contains references to the actual objects, and that would be a waste of memory since I won't ever need the contents of the actual objects. The best option I can think of is a HashSet of type Integer storing only the hash codes, but I'm wondering if there is a built-in data structure that would accomplish the same thing (and only accept one type as opposed to HashSet of type Integer which will accept the hash code of any object).










share|improve this question



















  • 4





    Is your hash function perfect? Or can you have multiple objects with the same hash value?

    – arshajii
    7 hours ago






  • 6





    what about hashing collisions?

    – Nathan Hughes台湾不在中国
    7 hours ago






  • 7





    The HashSet will contain a reference to your object, not a copy, so don't worry about space. A HashSet<Integer> would probably use up more space because it has references to integers.

    – Sweeper
    7 hours ago












  • I agree with @Sweeper, unless you have a real need for super-duper optimization. Also, your second idea with storing hashcodes as integer wouln't be more efficient as it would store the hash+the hash of the hash.

    – Joel
    7 hours ago











  • @Sweeper The HashSet uses internally a HashMap. The memory space is the same.

    – Octavian R.
    7 hours ago














8












8








8


1






My use-case is that I'm looking for a data structure in Java that will let me see if an object with the same hash code is inside (by calling contains()), but I will never need to iterate through the elements or retrieve the actual objects. A HashSet is close, but from my understanding, it still contains references to the actual objects, and that would be a waste of memory since I won't ever need the contents of the actual objects. The best option I can think of is a HashSet of type Integer storing only the hash codes, but I'm wondering if there is a built-in data structure that would accomplish the same thing (and only accept one type as opposed to HashSet of type Integer which will accept the hash code of any object).










share|improve this question
















My use-case is that I'm looking for a data structure in Java that will let me see if an object with the same hash code is inside (by calling contains()), but I will never need to iterate through the elements or retrieve the actual objects. A HashSet is close, but from my understanding, it still contains references to the actual objects, and that would be a waste of memory since I won't ever need the contents of the actual objects. The best option I can think of is a HashSet of type Integer storing only the hash codes, but I'm wondering if there is a built-in data structure that would accomplish the same thing (and only accept one type as opposed to HashSet of type Integer which will accept the hash code of any object).







java hashset






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited 7 hours ago







B Yellow

















asked 7 hours ago









B YellowB Yellow

463




463







  • 4





    Is your hash function perfect? Or can you have multiple objects with the same hash value?

    – arshajii
    7 hours ago






  • 6





    what about hashing collisions?

    – Nathan Hughes台湾不在中国
    7 hours ago






  • 7





    The HashSet will contain a reference to your object, not a copy, so don't worry about space. A HashSet<Integer> would probably use up more space because it has references to integers.

    – Sweeper
    7 hours ago












  • I agree with @Sweeper, unless you have a real need for super-duper optimization. Also, your second idea with storing hashcodes as integer wouln't be more efficient as it would store the hash+the hash of the hash.

    – Joel
    7 hours ago











  • @Sweeper The HashSet uses internally a HashMap. The memory space is the same.

    – Octavian R.
    7 hours ago













  • 4





    Is your hash function perfect? Or can you have multiple objects with the same hash value?

    – arshajii
    7 hours ago






  • 6





    what about hashing collisions?

    – Nathan Hughes台湾不在中国
    7 hours ago






  • 7





    The HashSet will contain a reference to your object, not a copy, so don't worry about space. A HashSet<Integer> would probably use up more space because it has references to integers.

    – Sweeper
    7 hours ago












  • I agree with @Sweeper, unless you have a real need for super-duper optimization. Also, your second idea with storing hashcodes as integer wouln't be more efficient as it would store the hash+the hash of the hash.

    – Joel
    7 hours ago











  • @Sweeper The HashSet uses internally a HashMap. The memory space is the same.

    – Octavian R.
    7 hours ago








4




4





Is your hash function perfect? Or can you have multiple objects with the same hash value?

– arshajii
7 hours ago





Is your hash function perfect? Or can you have multiple objects with the same hash value?

– arshajii
7 hours ago




6




6





what about hashing collisions?

– Nathan Hughes台湾不在中国
7 hours ago





what about hashing collisions?

– Nathan Hughes台湾不在中国
7 hours ago




7




7





The HashSet will contain a reference to your object, not a copy, so don't worry about space. A HashSet<Integer> would probably use up more space because it has references to integers.

– Sweeper
7 hours ago






The HashSet will contain a reference to your object, not a copy, so don't worry about space. A HashSet<Integer> would probably use up more space because it has references to integers.

– Sweeper
7 hours ago














I agree with @Sweeper, unless you have a real need for super-duper optimization. Also, your second idea with storing hashcodes as integer wouln't be more efficient as it would store the hash+the hash of the hash.

– Joel
7 hours ago





I agree with @Sweeper, unless you have a real need for super-duper optimization. Also, your second idea with storing hashcodes as integer wouln't be more efficient as it would store the hash+the hash of the hash.

– Joel
7 hours ago













@Sweeper The HashSet uses internally a HashMap. The memory space is the same.

– Octavian R.
7 hours ago






@Sweeper The HashSet uses internally a HashMap. The memory space is the same.

– Octavian R.
7 hours ago













4 Answers
4






active

oldest

votes


















9














A Bloom filter can tell whether an object might be a member, or is definitely not a member. You can control the likelihood of false positives. A single bit is stored per hash value.



The Guava library provides an implementation in Java.






share|improve this answer

























  • Nice. This seems like the solution for very low storage overhead. But you have to worry about the false negative case. If you can statistically eliminate that, this is great!

    – Steve
    6 hours ago







  • 1





    False positives, but you can control their probability. Another disadvantage is that you can't remove elements.

    – Andy Thomas
    6 hours ago











  • The question was for a data structure that checks using only the predefined hashCode(), which can potentially have 2^31 values (counting only positives). A Bloom filter that uses one hash function with 2 ^ 31 possible values would be extraordinarily large, seeing as it is basically just a BitSet. I don't see how that counts as "very low storage overhead".

    – Leo Aso
    6 hours ago



















1














If you want to track if a hash code is already present and to do it memory efficient a BitSet may suite your requirements.



Look at the following example:



 public static void main(String[] args) 
BitSet hashCodes = new BitSet();
hashCodes.set("1".hashCode());

System.out.println(hashCodes.get("1".hashCode())); // true
System.out.println(hashCodes.get("2".hashCode())); // false



The BitSet "implements a vector of bits that grows as needed.". It's a JDK "built-in data structure" which doesn't contain "references to the actual objects". It stores only if "the same hash code is inside".



EDIT:

As @Steve mentioned in his comment the implementation of the BitSet isn't the most memory efficient one. But there are more memory efficient implementations of a bit set - though not built-in.






share|improve this answer

























  • I don't know how a BitSet stores individual bits. Since obviously this usage will spread bits across a very large input domain, are you sure those are stored efficiently? Just asking. The naive assumption is that the structure would be an array of bytes, where the array was just expanded to include any bit position and all positions before that, which would be monstrously inefficient. But I don't know how it actually represents bits spread way apart.

    – Steve
    6 hours ago











  • It appears that your solution won't work. See github.com/brettwooldridge/SparseBitSet

    – Steve
    6 hours ago











  • @Steve You're right. Found additionally this post. But the idea of an bit set is basically not bad. It's rather the implementation of the JDK BitSet.

    – LuCio
    6 hours ago












  • It would be pretty efficient when about half of the possible values used... (unlikely in practice but still...)

    – Alexei Levenkov
    2 hours ago


















0














You could use a primitive collection implementation like IntSet to store values of hash codes. Obviously as others have mentioned this assumes collisions aren't a problem.






share|improve this answer






























    -1














    There is no such built-in data structure, because such a data structure is rarely needed. It's easy to build one, though.



    public class HashCodeSet<T> 

    private final HashSet<Integer> hashCodes;

    public MyHashSet()
    hashCodes = new HashSet<>();


    public MyHashSet(int initialCapacity)
    hashCodes = new HashSet<>(initialCapacity);


    public HashCodeSet(HashCodeSet toCopy)
    hashCodes = new HashSet<>(toCopy.hashCodes);


    public void add(T element)
    hashCodes.add(element.hashCode());


    public boolean containsHashCodeOf(T element)
    return hashCodes.contains(element.hashCode());


    @Override
    public boolean equals(o: Object)
    return o == this

    @Override
    public int hashCode()
    return hashCodes.hashCode(); // hash-ception


    @Override
    public String toString()
    return hashCodes.toString();







    share|improve this answer


















    • 1





      I think the OP's question wasn't about API, but about memory usage. This doesn't help with that since the result still acts like a HashSet.

      – Steve
      6 hours ago











    • I realize that I was unfair completely on this. I've removed my objections. Feel free to delete your comments on my comments. I still think there's something more to the problem, but I was off base. Sorry

      – Steve
      6 hours ago










    Your Answer






    StackExchange.ifUsing("editor", function ()
    StackExchange.using("externalEditor", function ()
    StackExchange.using("snippets", function ()
    StackExchange.snippets.init();
    );
    );
    , "code-snippets");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "1"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader:
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    ,
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );













    draft saved

    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55190768%2fis-there-a-data-structure-that-only-stores-hash-codes-and-not-the-actual-objects%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown

























    4 Answers
    4






    active

    oldest

    votes








    4 Answers
    4






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    9














    A Bloom filter can tell whether an object might be a member, or is definitely not a member. You can control the likelihood of false positives. A single bit is stored per hash value.



    The Guava library provides an implementation in Java.






    share|improve this answer

























    • Nice. This seems like the solution for very low storage overhead. But you have to worry about the false negative case. If you can statistically eliminate that, this is great!

      – Steve
      6 hours ago







    • 1





      False positives, but you can control their probability. Another disadvantage is that you can't remove elements.

      – Andy Thomas
      6 hours ago











    • The question was for a data structure that checks using only the predefined hashCode(), which can potentially have 2^31 values (counting only positives). A Bloom filter that uses one hash function with 2 ^ 31 possible values would be extraordinarily large, seeing as it is basically just a BitSet. I don't see how that counts as "very low storage overhead".

      – Leo Aso
      6 hours ago
















    9














    A Bloom filter can tell whether an object might be a member, or is definitely not a member. You can control the likelihood of false positives. A single bit is stored per hash value.



    The Guava library provides an implementation in Java.






    share|improve this answer

























    • Nice. This seems like the solution for very low storage overhead. But you have to worry about the false negative case. If you can statistically eliminate that, this is great!

      – Steve
      6 hours ago







    • 1





      False positives, but you can control their probability. Another disadvantage is that you can't remove elements.

      – Andy Thomas
      6 hours ago











    • The question was for a data structure that checks using only the predefined hashCode(), which can potentially have 2^31 values (counting only positives). A Bloom filter that uses one hash function with 2 ^ 31 possible values would be extraordinarily large, seeing as it is basically just a BitSet. I don't see how that counts as "very low storage overhead".

      – Leo Aso
      6 hours ago














    9












    9








    9







    A Bloom filter can tell whether an object might be a member, or is definitely not a member. You can control the likelihood of false positives. A single bit is stored per hash value.



    The Guava library provides an implementation in Java.






    share|improve this answer















    A Bloom filter can tell whether an object might be a member, or is definitely not a member. You can control the likelihood of false positives. A single bit is stored per hash value.



    The Guava library provides an implementation in Java.







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited 6 hours ago

























    answered 6 hours ago









    Andy ThomasAndy Thomas

    68.1k980133




    68.1k980133












    • Nice. This seems like the solution for very low storage overhead. But you have to worry about the false negative case. If you can statistically eliminate that, this is great!

      – Steve
      6 hours ago







    • 1





      False positives, but you can control their probability. Another disadvantage is that you can't remove elements.

      – Andy Thomas
      6 hours ago











    • The question was for a data structure that checks using only the predefined hashCode(), which can potentially have 2^31 values (counting only positives). A Bloom filter that uses one hash function with 2 ^ 31 possible values would be extraordinarily large, seeing as it is basically just a BitSet. I don't see how that counts as "very low storage overhead".

      – Leo Aso
      6 hours ago


















    • Nice. This seems like the solution for very low storage overhead. But you have to worry about the false negative case. If you can statistically eliminate that, this is great!

      – Steve
      6 hours ago







    • 1





      False positives, but you can control their probability. Another disadvantage is that you can't remove elements.

      – Andy Thomas
      6 hours ago











    • The question was for a data structure that checks using only the predefined hashCode(), which can potentially have 2^31 values (counting only positives). A Bloom filter that uses one hash function with 2 ^ 31 possible values would be extraordinarily large, seeing as it is basically just a BitSet. I don't see how that counts as "very low storage overhead".

      – Leo Aso
      6 hours ago

















    Nice. This seems like the solution for very low storage overhead. But you have to worry about the false negative case. If you can statistically eliminate that, this is great!

    – Steve
    6 hours ago






    Nice. This seems like the solution for very low storage overhead. But you have to worry about the false negative case. If you can statistically eliminate that, this is great!

    – Steve
    6 hours ago





    1




    1





    False positives, but you can control their probability. Another disadvantage is that you can't remove elements.

    – Andy Thomas
    6 hours ago





    False positives, but you can control their probability. Another disadvantage is that you can't remove elements.

    – Andy Thomas
    6 hours ago













    The question was for a data structure that checks using only the predefined hashCode(), which can potentially have 2^31 values (counting only positives). A Bloom filter that uses one hash function with 2 ^ 31 possible values would be extraordinarily large, seeing as it is basically just a BitSet. I don't see how that counts as "very low storage overhead".

    – Leo Aso
    6 hours ago






    The question was for a data structure that checks using only the predefined hashCode(), which can potentially have 2^31 values (counting only positives). A Bloom filter that uses one hash function with 2 ^ 31 possible values would be extraordinarily large, seeing as it is basically just a BitSet. I don't see how that counts as "very low storage overhead".

    – Leo Aso
    6 hours ago














    1














    If you want to track if a hash code is already present and to do it memory efficient a BitSet may suite your requirements.



    Look at the following example:



     public static void main(String[] args) 
    BitSet hashCodes = new BitSet();
    hashCodes.set("1".hashCode());

    System.out.println(hashCodes.get("1".hashCode())); // true
    System.out.println(hashCodes.get("2".hashCode())); // false



    The BitSet "implements a vector of bits that grows as needed.". It's a JDK "built-in data structure" which doesn't contain "references to the actual objects". It stores only if "the same hash code is inside".



    EDIT:

    As @Steve mentioned in his comment the implementation of the BitSet isn't the most memory efficient one. But there are more memory efficient implementations of a bit set - though not built-in.






    share|improve this answer

























    • I don't know how a BitSet stores individual bits. Since obviously this usage will spread bits across a very large input domain, are you sure those are stored efficiently? Just asking. The naive assumption is that the structure would be an array of bytes, where the array was just expanded to include any bit position and all positions before that, which would be monstrously inefficient. But I don't know how it actually represents bits spread way apart.

      – Steve
      6 hours ago











    • It appears that your solution won't work. See github.com/brettwooldridge/SparseBitSet

      – Steve
      6 hours ago











    • @Steve You're right. Found additionally this post. But the idea of an bit set is basically not bad. It's rather the implementation of the JDK BitSet.

      – LuCio
      6 hours ago












    • It would be pretty efficient when about half of the possible values used... (unlikely in practice but still...)

      – Alexei Levenkov
      2 hours ago















    1














    If you want to track if a hash code is already present and to do it memory efficient a BitSet may suite your requirements.



    Look at the following example:



     public static void main(String[] args) 
    BitSet hashCodes = new BitSet();
    hashCodes.set("1".hashCode());

    System.out.println(hashCodes.get("1".hashCode())); // true
    System.out.println(hashCodes.get("2".hashCode())); // false



    The BitSet "implements a vector of bits that grows as needed.". It's a JDK "built-in data structure" which doesn't contain "references to the actual objects". It stores only if "the same hash code is inside".



    EDIT:

    As @Steve mentioned in his comment the implementation of the BitSet isn't the most memory efficient one. But there are more memory efficient implementations of a bit set - though not built-in.






    share|improve this answer

























    • I don't know how a BitSet stores individual bits. Since obviously this usage will spread bits across a very large input domain, are you sure those are stored efficiently? Just asking. The naive assumption is that the structure would be an array of bytes, where the array was just expanded to include any bit position and all positions before that, which would be monstrously inefficient. But I don't know how it actually represents bits spread way apart.

      – Steve
      6 hours ago











    • It appears that your solution won't work. See github.com/brettwooldridge/SparseBitSet

      – Steve
      6 hours ago











    • @Steve You're right. Found additionally this post. But the idea of an bit set is basically not bad. It's rather the implementation of the JDK BitSet.

      – LuCio
      6 hours ago












    • It would be pretty efficient when about half of the possible values used... (unlikely in practice but still...)

      – Alexei Levenkov
      2 hours ago













    1












    1








    1







    If you want to track if a hash code is already present and to do it memory efficient a BitSet may suite your requirements.



    Look at the following example:



     public static void main(String[] args) 
    BitSet hashCodes = new BitSet();
    hashCodes.set("1".hashCode());

    System.out.println(hashCodes.get("1".hashCode())); // true
    System.out.println(hashCodes.get("2".hashCode())); // false



    The BitSet "implements a vector of bits that grows as needed.". It's a JDK "built-in data structure" which doesn't contain "references to the actual objects". It stores only if "the same hash code is inside".



    EDIT:

    As @Steve mentioned in his comment the implementation of the BitSet isn't the most memory efficient one. But there are more memory efficient implementations of a bit set - though not built-in.






    share|improve this answer















    If you want to track if a hash code is already present and to do it memory efficient a BitSet may suite your requirements.



    Look at the following example:



     public static void main(String[] args) 
    BitSet hashCodes = new BitSet();
    hashCodes.set("1".hashCode());

    System.out.println(hashCodes.get("1".hashCode())); // true
    System.out.println(hashCodes.get("2".hashCode())); // false



    The BitSet "implements a vector of bits that grows as needed.". It's a JDK "built-in data structure" which doesn't contain "references to the actual objects". It stores only if "the same hash code is inside".



    EDIT:

    As @Steve mentioned in his comment the implementation of the BitSet isn't the most memory efficient one. But there are more memory efficient implementations of a bit set - though not built-in.







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited 6 hours ago

























    answered 6 hours ago









    LuCioLuCio

    2,8821924




    2,8821924












    • I don't know how a BitSet stores individual bits. Since obviously this usage will spread bits across a very large input domain, are you sure those are stored efficiently? Just asking. The naive assumption is that the structure would be an array of bytes, where the array was just expanded to include any bit position and all positions before that, which would be monstrously inefficient. But I don't know how it actually represents bits spread way apart.

      – Steve
      6 hours ago











    • It appears that your solution won't work. See github.com/brettwooldridge/SparseBitSet

      – Steve
      6 hours ago











    • @Steve You're right. Found additionally this post. But the idea of an bit set is basically not bad. It's rather the implementation of the JDK BitSet.

      – LuCio
      6 hours ago












    • It would be pretty efficient when about half of the possible values used... (unlikely in practice but still...)

      – Alexei Levenkov
      2 hours ago

















    • I don't know how a BitSet stores individual bits. Since obviously this usage will spread bits across a very large input domain, are you sure those are stored efficiently? Just asking. The naive assumption is that the structure would be an array of bytes, where the array was just expanded to include any bit position and all positions before that, which would be monstrously inefficient. But I don't know how it actually represents bits spread way apart.

      – Steve
      6 hours ago











    • It appears that your solution won't work. See github.com/brettwooldridge/SparseBitSet

      – Steve
      6 hours ago











    • @Steve You're right. Found additionally this post. But the idea of an bit set is basically not bad. It's rather the implementation of the JDK BitSet.

      – LuCio
      6 hours ago












    • It would be pretty efficient when about half of the possible values used... (unlikely in practice but still...)

      – Alexei Levenkov
      2 hours ago
















    I don't know how a BitSet stores individual bits. Since obviously this usage will spread bits across a very large input domain, are you sure those are stored efficiently? Just asking. The naive assumption is that the structure would be an array of bytes, where the array was just expanded to include any bit position and all positions before that, which would be monstrously inefficient. But I don't know how it actually represents bits spread way apart.

    – Steve
    6 hours ago





    I don't know how a BitSet stores individual bits. Since obviously this usage will spread bits across a very large input domain, are you sure those are stored efficiently? Just asking. The naive assumption is that the structure would be an array of bytes, where the array was just expanded to include any bit position and all positions before that, which would be monstrously inefficient. But I don't know how it actually represents bits spread way apart.

    – Steve
    6 hours ago













    It appears that your solution won't work. See github.com/brettwooldridge/SparseBitSet

    – Steve
    6 hours ago





    It appears that your solution won't work. See github.com/brettwooldridge/SparseBitSet

    – Steve
    6 hours ago













    @Steve You're right. Found additionally this post. But the idea of an bit set is basically not bad. It's rather the implementation of the JDK BitSet.

    – LuCio
    6 hours ago






    @Steve You're right. Found additionally this post. But the idea of an bit set is basically not bad. It's rather the implementation of the JDK BitSet.

    – LuCio
    6 hours ago














    It would be pretty efficient when about half of the possible values used... (unlikely in practice but still...)

    – Alexei Levenkov
    2 hours ago





    It would be pretty efficient when about half of the possible values used... (unlikely in practice but still...)

    – Alexei Levenkov
    2 hours ago











    0














    You could use a primitive collection implementation like IntSet to store values of hash codes. Obviously as others have mentioned this assumes collisions aren't a problem.






    share|improve this answer



























      0














      You could use a primitive collection implementation like IntSet to store values of hash codes. Obviously as others have mentioned this assumes collisions aren't a problem.






      share|improve this answer

























        0












        0








        0







        You could use a primitive collection implementation like IntSet to store values of hash codes. Obviously as others have mentioned this assumes collisions aren't a problem.






        share|improve this answer













        You could use a primitive collection implementation like IntSet to store values of hash codes. Obviously as others have mentioned this assumes collisions aren't a problem.







        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered 6 hours ago









        MarkMark

        24.2k44783




        24.2k44783





















            -1














            There is no such built-in data structure, because such a data structure is rarely needed. It's easy to build one, though.



            public class HashCodeSet<T> 

            private final HashSet<Integer> hashCodes;

            public MyHashSet()
            hashCodes = new HashSet<>();


            public MyHashSet(int initialCapacity)
            hashCodes = new HashSet<>(initialCapacity);


            public HashCodeSet(HashCodeSet toCopy)
            hashCodes = new HashSet<>(toCopy.hashCodes);


            public void add(T element)
            hashCodes.add(element.hashCode());


            public boolean containsHashCodeOf(T element)
            return hashCodes.contains(element.hashCode());


            @Override
            public boolean equals(o: Object)
            return o == this

            @Override
            public int hashCode()
            return hashCodes.hashCode(); // hash-ception


            @Override
            public String toString()
            return hashCodes.toString();







            share|improve this answer


















            • 1





              I think the OP's question wasn't about API, but about memory usage. This doesn't help with that since the result still acts like a HashSet.

              – Steve
              6 hours ago











            • I realize that I was unfair completely on this. I've removed my objections. Feel free to delete your comments on my comments. I still think there's something more to the problem, but I was off base. Sorry

              – Steve
              6 hours ago















            -1














            There is no such built-in data structure, because such a data structure is rarely needed. It's easy to build one, though.



            public class HashCodeSet<T> 

            private final HashSet<Integer> hashCodes;

            public MyHashSet()
            hashCodes = new HashSet<>();


            public MyHashSet(int initialCapacity)
            hashCodes = new HashSet<>(initialCapacity);


            public HashCodeSet(HashCodeSet toCopy)
            hashCodes = new HashSet<>(toCopy.hashCodes);


            public void add(T element)
            hashCodes.add(element.hashCode());


            public boolean containsHashCodeOf(T element)
            return hashCodes.contains(element.hashCode());


            @Override
            public boolean equals(o: Object)
            return o == this

            @Override
            public int hashCode()
            return hashCodes.hashCode(); // hash-ception


            @Override
            public String toString()
            return hashCodes.toString();







            share|improve this answer


















            • 1





              I think the OP's question wasn't about API, but about memory usage. This doesn't help with that since the result still acts like a HashSet.

              – Steve
              6 hours ago











            • I realize that I was unfair completely on this. I've removed my objections. Feel free to delete your comments on my comments. I still think there's something more to the problem, but I was off base. Sorry

              – Steve
              6 hours ago













            -1












            -1








            -1







            There is no such built-in data structure, because such a data structure is rarely needed. It's easy to build one, though.



            public class HashCodeSet<T> 

            private final HashSet<Integer> hashCodes;

            public MyHashSet()
            hashCodes = new HashSet<>();


            public MyHashSet(int initialCapacity)
            hashCodes = new HashSet<>(initialCapacity);


            public HashCodeSet(HashCodeSet toCopy)
            hashCodes = new HashSet<>(toCopy.hashCodes);


            public void add(T element)
            hashCodes.add(element.hashCode());


            public boolean containsHashCodeOf(T element)
            return hashCodes.contains(element.hashCode());


            @Override
            public boolean equals(o: Object)
            return o == this

            @Override
            public int hashCode()
            return hashCodes.hashCode(); // hash-ception


            @Override
            public String toString()
            return hashCodes.toString();







            share|improve this answer













            There is no such built-in data structure, because such a data structure is rarely needed. It's easy to build one, though.



            public class HashCodeSet<T> 

            private final HashSet<Integer> hashCodes;

            public MyHashSet()
            hashCodes = new HashSet<>();


            public MyHashSet(int initialCapacity)
            hashCodes = new HashSet<>(initialCapacity);


            public HashCodeSet(HashCodeSet toCopy)
            hashCodes = new HashSet<>(toCopy.hashCodes);


            public void add(T element)
            hashCodes.add(element.hashCode());


            public boolean containsHashCodeOf(T element)
            return hashCodes.contains(element.hashCode());


            @Override
            public boolean equals(o: Object)
            return o == this

            @Override
            public int hashCode()
            return hashCodes.hashCode(); // hash-ception


            @Override
            public String toString()
            return hashCodes.toString();








            share|improve this answer












            share|improve this answer



            share|improve this answer










            answered 6 hours ago









            Leo AsoLeo Aso

            5,27211029




            5,27211029







            • 1





              I think the OP's question wasn't about API, but about memory usage. This doesn't help with that since the result still acts like a HashSet.

              – Steve
              6 hours ago











            • I realize that I was unfair completely on this. I've removed my objections. Feel free to delete your comments on my comments. I still think there's something more to the problem, but I was off base. Sorry

              – Steve
              6 hours ago












            • 1





              I think the OP's question wasn't about API, but about memory usage. This doesn't help with that since the result still acts like a HashSet.

              – Steve
              6 hours ago











            • I realize that I was unfair completely on this. I've removed my objections. Feel free to delete your comments on my comments. I still think there's something more to the problem, but I was off base. Sorry

              – Steve
              6 hours ago







            1




            1





            I think the OP's question wasn't about API, but about memory usage. This doesn't help with that since the result still acts like a HashSet.

            – Steve
            6 hours ago





            I think the OP's question wasn't about API, but about memory usage. This doesn't help with that since the result still acts like a HashSet.

            – Steve
            6 hours ago













            I realize that I was unfair completely on this. I've removed my objections. Feel free to delete your comments on my comments. I still think there's something more to the problem, but I was off base. Sorry

            – Steve
            6 hours ago





            I realize that I was unfair completely on this. I've removed my objections. Feel free to delete your comments on my comments. I still think there's something more to the problem, but I was off base. Sorry

            – Steve
            6 hours ago

















            draft saved

            draft discarded
















































            Thanks for contributing an answer to Stack Overflow!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid


            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.

            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55190768%2fis-there-a-data-structure-that-only-stores-hash-codes-and-not-the-actual-objects%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            名間水力發電廠 目录 沿革 設施 鄰近設施 註釋 外部連結 导航菜单23°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.7113923°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.71139計畫概要原始内容臺灣第一座BOT 模式開發的水力發電廠-名間水力電廠名間水力發電廠 水利署首件BOT案原始内容《小檔案》名間電廠 首座BOT水力發電廠原始内容名間電廠BOT - 經濟部水利署中區水資源局

            Prove that NP is closed under karp reduction?Space(n) not closed under Karp reductions - what about NTime(n)?Class P is closed under rotation?Prove or disprove that $NL$ is closed under polynomial many-one reductions$mathbfNC_2$ is closed under log-space reductionOn Karp reductionwhen can I know if a class (complexity) is closed under reduction (cook/karp)Check if class $PSPACE$ is closed under polyonomially space reductionIs NPSPACE also closed under polynomial-time reduction and under log-space reduction?Prove PSPACE is closed under complement?Prove PSPACE is closed under union?

            Is my guitar’s action too high? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Strings too stiff on a recently purchased acoustic guitar | Cort AD880CEIs the action of my guitar really high?Μy little finger is too weak to play guitarWith guitar, how long should I give my fingers to strengthen / callous?When playing a fret the guitar sounds mutedPlaying (Barre) chords up the guitar neckI think my guitar strings are wound too tight and I can't play barre chordsF barre chord on an SG guitarHow to find to the right strings of a barre chord by feel?High action on higher fret on my steel acoustic guitar