<div dir="ltr">Nick,<div><br></div><div>The mailing list is not answered by ATM or Google search engine, where you can play around with any questions you like. </div><div>It takes so much efforts for a person to understand the questions, and reply to that. You need to respect the value of a reply and the value of time spent by REAL people.</div>
<div><br></div><div>Look at your first question, and after a long reply from GREG, you are asking a totally different question.</div><div><br></div><div><br></div><div>Thanks</div><div>Ashok</div></div><div class="gmail_extra">
<br><br><div class="gmail_quote">On Tue, Aug 19, 2014 at 10:53 AM, Nick Krause <span dir="ltr"><<a href="mailto:xerofoify@gmail.com" target="_blank">xerofoify@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="HOEnZb"><div class="h5">On Mon, Aug 18, 2014 at 7:01 PM, Greg Freemyer <<a href="mailto:greg.freemyer@gmail.com">greg.freemyer@gmail.com</a>> wrote:<br>
> On Mon, Aug 18, 2014 at 4:20 PM, Nick Krause <<a href="mailto:xerofoify@gmail.com">xerofoify@gmail.com</a>> wrote:<br>
>> What are the advantages of the hashed linked list version over the<br>
>> standard one and does it<br>
>> increase the memory usage and overhead of the linked list more if I<br>
>> use a hashed version?<br>
><br>
> Seriously? Do you know what a hash is?<br>
><br>
> A hash is a well-defined many to one algorithm.<br>
><br>
> If I have a universe of a million items that hash down to 100 unique<br>
> hashes, then I can group those million items by hash and have 100<br>
> groups of roughly 10,000 items each.<br>
><br>
> The better the hashing algorithm versus my original universe of 1<br>
> million items, the more even the distribution.<br>
><br>
> Now that I have 100 segregated groups I can build an array of 100<br>
> linked lists all maintained separately.<br>
><br>
> Thus:<br>
><br>
> hash_index = my_hash(item)<br>
><br>
> add_item(linked_list[hash_item], item) is how I add my item to the<br>
> hashed linked list.<br>
><br>
> is_in_list(linked_list[hash_item], item) is how I check to see if my<br>
> item is already in the list.<br>
><br>
> So in my example I have to have 100 linked lists, but each list is on<br>
> average 100x smaller than a simple linked list would be.<br>
><br>
> Is adding an item to the hashed linked list faster?<br>
><br>
> Absolutely not, I have to hash the item first then do a normal linked<br>
> list insertion. That will always be slower.<br>
><br>
> Is finding the item faster?<br>
><br>
> That is the whole point of the exercise. The theory is you ONLY use a<br>
> hashed linked list if the overhead of hashing the item is less than<br>
> the amount of time saved by traversing shorter lists when you search.<br>
><br>
> It is the job of the programmer to make the determination if a hashed<br>
> list is a better choice or not on a case by case basis. It depends on<br>
> the length of the list without breaking it into pieces and how well<br>
> the hash algorithm can do at generating roughly similar segregated<br>
> groups.<br>
><br>
> For the size question, write yourself a userspace app and test it.<br>
> Obviously that is more work than asking here, but it is ASSUMED you<br>
> are doing research on your OWN before you post questions here.<br>
><br>
> fyi: this question has little to do with the linux kernel. It is part<br>
> of what people mean when they say you need to go learn c before you<br>
> start on the kernel. Using linked lists and hashed linked lists is<br>
> stuff you can fully explore in userspace.<br>
><br>
> Greg<br>
</div></div>No I known what the advantages are for user space was wondering if<br>
there were any issues that differ in<br>
kernel space.<br>
<span class="HOEnZb"><font color="#888888">Nick<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
_______________________________________________<br>
Kernelnewbies mailing list<br>
<a href="mailto:Kernelnewbies@kernelnewbies.org">Kernelnewbies@kernelnewbies.org</a><br>
<a href="http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies" target="_blank">http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies</a><br>
</div></div></blockquote></div><br></div>