Write a copy of Dictionary and Foreach implementation and summary
- 2020-05-27 04:43:31
- OfStack
Write your own class to mimic the Dictionary implementation
a, custom dictionary class MyDic
b, call test
The test results in b showed that they did not imitate. Why is the speed provided by Net FrameWork?
Answer: in Dictionary, there is an area for storing key-value pairs. Each storage location in this area has an address number. According to hashCode algorithm, calculate the address that the key-value pair of key should be stored, and put the key-value pair into the specified address. When searching, first calculate the address of key, you can find the data. Look for room Numbers based on key, rather than room by room. (*) or: when taking 1 kvp, a fixed algorithm (hash algorithm) is used to calculate the address of this kvp based on key. You can quickly calculate the address of kvp based on the key you are looking for.
It is easy to answer the interview question "what interface does Foreach implement?" but can we imitate the implementation of Foreach?
Internal principles of c, Foreach: the IEnumerable interface implements IEnumerable itself
d, call your own IEnumerable
Conclusion:
If a class does foreach, the class must implement IEnumerable, the collection must support foreach traversal, and the IEnumerable interface must be implemented (and return objects that implement IEnumerator in some way)
a, custom dictionary class MyDic
using System.Collections.Generic;
namespace _10_ Write their own Dictionary {
class KeyValuePair {
public KeyValuePair() {
}
public KeyValuePair(string key, string value) {
this.key = key;
this.value = value;
}
private string key;
public string Key {
get {
return key;
}
set {
key = value;
}
}
private string value;
public string Value {
get {
return this .value;
}
set {
this.value = value ;
}
}
}
class MyDic {
List<KeyValuePair > list = new List<KeyValuePair >();
public void Add(string key, string value) {
list.Add( new KeyValuePair (key, value));
}
public bool ContainsKey(string key) {
bool res = false ;
foreach(KeyValuePair item in list) {
if(item.Key == key) {
res = true;
break;
}
}
return res;
}
}
}
b, call test
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
namespace _10_ Write their own Dictionary {
class Program {
static void Main(string[] args) {
//Dictionary Method implementation
Dictionary<string , string> dic = new Dictionary <string, string>();
string[] filecon = File .ReadAllLines(" The english-chinese dictionary TXT format .txt", Encoding.Default);
for(int i = 0; i < filecon.Count(); i++) {
string[] arr = filecon[i].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
if(!dic.ContainsKey(arr[0])) {
dic.Add(arr[0], arr[1]);
}
}
Stopwatch sw = new Stopwatch();
sw.Start();
dic.ContainsKey( "china");
sw.Stop();
Console.WriteLine(sw.Elapsed);//00:00:00:0000055;
// His writing list implementation
MyDic mydic = new MyDic();
string[] filecon2 = File .ReadAllLines(" The english-chinese dictionary TXT format .txt", Encoding.Default);
for(int i = 0; i < filecon2.Count(); i++) {
string[] arr = filecon2[i].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
if(!mydic.ContainsKey(arr[0])) {
mydic.Add(arr[0], arr[1]);
}
}
Stopwatch sw2 = new Stopwatch();
sw2.Start();
mydic.ContainsKey( "china");
sw2.Stop();
Console.WriteLine(sw2.Elapsed);//00:00:00:0001287; How many times slower!! because dictionary than list More dictionary directories
Console.Read();
}
}
}
The test results in b showed that they did not imitate. Why is the speed provided by Net FrameWork?
Answer: in Dictionary, there is an area for storing key-value pairs. Each storage location in this area has an address number. According to hashCode algorithm, calculate the address that the key-value pair of key should be stored, and put the key-value pair into the specified address. When searching, first calculate the address of key, you can find the data. Look for room Numbers based on key, rather than room by room. (*) or: when taking 1 kvp, a fixed algorithm (hash algorithm) is used to calculate the address of this kvp based on key. You can quickly calculate the address of kvp based on the key you are looking for.
It is easy to answer the interview question "what interface does Foreach implement?" but can we imitate the implementation of Foreach?
Internal principles of c, Foreach: the IEnumerable interface implements IEnumerable itself
using System.Collections;// The introduction of IEnumerable Host namespace
namespace IEnumerater {
class MyList : IEnumerable {// Implementing an interface IEnumerable It is 1 a IEnumerator Declare the method of the enumerator
ArrayList ary = new ArrayList();
public void Add(string name) {
ary.Add(name);
}
// Write your own indexer Formal similar attribute Function like enumeration A quick and easy way Access the elements in the collection
public string this[ int index] {//int type
get {
return ary[index].ToString();
} //index>ary.Count When the index limit is exceeded
//set { }
}
public int this[ string name] {//string type through name Search index Parameter types are up to you The return type is up to you
get {
for(int i = 0; i < ary.Count; i++) {
if(ary[i] == name) {
return i;
}
}
return -1;
}
}
public IEnumerator GetEnumerator() {//IEnumerator F12 The jump definition can be found here foreach Only data can be read, not modified
for(int i = 0; i < ary.Count; i++) {
yield return ary[i].ToString();// yield The keyword You can see implementation IEnumerator( The enumerator ) In the interface MoveNext( Point to the 1 article ) methods and Current( Get the current element Because only get So it makes sense why foreach The reason why the value cannot be changed ) As well as Reset Reset the index
}
}
}
}
d, call your own IEnumerable
using System;
namespace IEnumerater {
class Program {
static void Main(string[] args) {
// Write their own 1 A class To achieve the IEnumerable Of the interface getEnumerator() methods You can do that foreach The operation of the
MyList mylist = new MyList();
mylist.Add( "wanghao");// Call your own add(string) methods
mylist.Add( "nihao");
mylist.Add( "buhao");
Console.WriteLine(mylist[1]);// Use your own index
Console.WriteLine(mylist["nihao" ].ToString());
foreach(string item in mylist) {
Console.WriteLine(item);
//item = "hello"; You can't use foreach Change the value
}
Console.Read();
}
}
}
Conclusion:
If a class does foreach, the class must implement IEnumerable, the collection must support foreach traversal, and the IEnumerable interface must be implemented (and return objects that implement IEnumerator in some way)