.net - HashSet vs. List performance -

it's clear search performance of generic hashset<t> class higher of generic list<t> class. compare hash-based key linear approach in list<t> class.

however calculating hash key may take cpu cycles, small amount of items linear search can real alternative hashset<t>.

my question: break-even?

to simplify scenario (and fair) let's assume list<t> class uses element's equals() method identify item.

a lot of people saying once size speed concern hashset<t> beat list<t>, depends on doing.

let's have list<t> ever have on average 5 items in it. on large number of cycles, if single item added or removed each cycle, may better off using list<t>.

i did test on machine, and, well, has very small advantage list<t>. list of short strings, advantage went away after size 5, objects after size 20.

1 item list strs time: 617ms 1 item hashset strs time: 1332ms  2 item list strs time: 781ms 2 item hashset strs time: 1354ms  3 item list strs time: 950ms 3 item hashset strs time: 1405ms  4 item list strs time: 1126ms 4 item hashset strs time: 1441ms  5 item list strs time: 1370ms 5 item hashset strs time: 1452ms  6 item list strs time: 1481ms 6 item hashset strs time: 1418ms  7 item list strs time: 1581ms 7 item hashset strs time: 1464ms  8 item list strs time: 1726ms 8 item hashset strs time: 1398ms  9 item list strs time: 1901ms 9 item hashset strs time: 1433ms  1 item list objs time: 614ms 1 item hashset objs time: 1993ms  4 item list objs time: 837ms 4 item hashset objs time: 1914ms  7 item list objs time: 1070ms 7 item hashset objs time: 1900ms  10 item list objs time: 1267ms 10 item hashset objs time: 1904ms  13 item list objs time: 1494ms 13 item hashset objs time: 1893ms  16 item list objs time: 1695ms 16 item hashset objs time: 1879ms  19 item list objs time: 1902ms 19 item hashset objs time: 1950ms  22 item list objs time: 2136ms 22 item hashset objs time: 1893ms  25 item list objs time: 2357ms 25 item hashset objs time: 1826ms  28 item list objs time: 2555ms 28 item hashset objs time: 1865ms  31 item list objs time: 2755ms 31 item hashset objs time: 1963ms  34 item list objs time: 3025ms 34 item hashset objs time: 1874ms  37 item list objs time: 3195ms 37 item hashset objs time: 1958ms  40 item list objs time: 3401ms 40 item hashset objs time: 1855ms  43 item list objs time: 3618ms 43 item hashset objs time: 1869ms  46 item list objs time: 3883ms 46 item hashset objs time: 2046ms  49 item list objs time: 4218ms 49 item hashset objs time: 1873ms 

here data displayed graph:

here's code:

static void main(string[] args) {     int times = 10000000;       (int listsize = 1; listsize < 10; listsize++)     {         list<string> list = new list<string>();         hashset<string> hashset = new hashset<string>();          (int = 0; < listsize; i++)         {             list.add("string" + i.tostring());             hashset.add("string" + i.tostring());         }          stopwatch timer = new stopwatch();         timer.start();         (int = 0; < times; i++)         {             list.remove("string0");             list.add("string0");         }         timer.stop();         console.writeline(listsize.tostring() + " item list strs time: " + timer.elapsedmilliseconds.tostring() + "ms");           timer = new stopwatch();         timer.start();         (int = 0; < times; i++)         {             hashset.remove("string0");             hashset.add("string0");         }         timer.stop();         console.writeline(listsize.tostring() + " item hashset strs time: " + timer.elapsedmilliseconds.tostring() + "ms");         console.writeline();     }       (int listsize = 1; listsize < 50; listsize+=3)     {         list<object> list = new list<object>();         hashset<object> hashset = new hashset<object>();          (int = 0; < listsize; i++)         {             list.add(new object());             hashset.add(new object());         }          object objtoaddrem = list[0];          stopwatch timer = new stopwatch();         timer.start();         (int = 0; < times; i++)         {             list.remove(objtoaddrem);             list.add(objtoaddrem);         }         timer.stop();         console.writeline(listsize.tostring() + " item list objs time: " + timer.elapsedmilliseconds.tostring() + "ms");            timer = new stopwatch();         timer.start();         (int = 0; < times; i++)         {             hashset.remove(objtoaddrem);             hashset.add(objtoaddrem);         }         timer.stop();         console.writeline(listsize.tostring() + " item hashset objs time: " + timer.elapsedmilliseconds.tostring() + "ms");         console.writeline();     }      console.readline(); }