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