Go语言slice基本操作

//删除
func remove(slice []interface{}, i int) []interface{} {
    //    copy(slice[i:], slice[i+1:])
    //    return slice[:len(slice)-1]
    return append(slice[:i], slice[i+1:]...)
}

//新增
func add(slice []interface{}, value interface{}) []interface{} {
    return append(slice, value)
}

// 插入尽量不要采用make新变量+append的方式,效率很低

//插入1
func insert(slice *[]interface{}, index int, value interface{}) {
    rear := append([]interface{}{}, (*slice)[index:]...)
    *slice = append(append((*slice)[:index], value), rear...)
}

// 插入2
func insert(slice []interface{}, index int, value interface{}) {
    rear  := append([]interface{}{}, slice[index : ]...)
    slice  = append(slice[0 : index], value)
    slice  = append(slice, rear...)
    return slice
}

//修改
func update(slice []interface{}, index int, value interface{}) {
    slice[index] = value
}

//查找
func find(slice []interface{}, index int) interface{} {
    return slice[index]
}

//清空slice
func empty(slice *[]interface{}) {
    //    *slice = nil
    *slice = append([]interface{}{})
}

//遍历
func list(slice []interface{}) {
    for _, v := range slice {
        fmt.Printf("%d ", v)
    }
}

 

Go使用mmap的例子

package main

import (
	"fmt"
	"os"
	"syscall"
	"unsafe"
	)

func main() {
	n := 1000
	t := int(unsafe.Sizeof(0)) * n

	map_file, _ := os.Create("/tmp/test.dat")
	_, _ = map_file.Seek(int64(t - 1), 0)
	map_file.Write([]byte(" "))

	mmap, _ := syscall.Mmap(map_file.Fd(), 0, int(t), syscall.PROT_READ | syscall.PROT_WRITE, syscall.MAP_SHARED)
	map_array := (*[1000]int)(unsafe.Pointer(&mmap))

	for i:=0; i < n; i++ {
		map_array[i] = i*i
	}

	fmt.Println(*map_array)
}

 

Go之strings、buffers、bytes、binary包

strings包

strings包的使用举例:

package main
import s "strings"
import "fmt"

var p = fmt.Println

func main() {
    p("Contains:  ", s.Contains("test", "es"))
    p("Count:     ", s.Count("test", "t"))
    p("HasPrefix: ", s.HasPrefix("test", "te"))
    p("HasSuffix: ", s.HasSuffix("test", "st"))
    p("Index:     ", s.Index("test", "e"))
    p("Join:      ", s.Join([]string{"a", "b"}, "-"))
    p("Repeat:    ", s.Repeat("a", 5))
    p("Replace:   ", s.Replace("foo", "o", "0", -1))
    p("Replace:   ", s.Replace("foo", "o", "0", 1))
    p("Split:     ", s.Split("a-b-c-d-e", "-"))
    p("ToLower:   ", s.ToLower("TEST"))
    p("ToUpper:   ", s.ToUpper("test"))
    p()
    p("Len: ", len("hello"))
    p("Char:", "hello"[1])
}

Continue reading "Go之strings、buffers、bytes、binary包"

Go语言实现的常用哈希函数,并提供对应的64位方法

以下是使用Go语言实现的常用哈希函数(BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash),并提供每个哈希对应的64位方法。经测试,64位的哈希函数基本不会出现碰撞(测试数据为十亿随机字符串数据量)。

哈希函数代码库地址:https://gitee.com/johng/gf/tree/master/src/g/encoding/ghash

// 封装常用的hash函数
package ghash


// BKDR Hash Function
func BKDRHash(str []byte) uint32 {
    var seed uint32 = 131; // 31 131 1313 13131 131313 etc..
    var hash uint32 = 0;
    for i := 0; i < len(str); i++ {
        hash = hash * seed + uint32(str[i])
    }
    return (hash & 0x7FFFFFFF)
}

// BKDR Hash Function 64
func BKDRHash64(str []byte) uint64 {
    var seed uint64 = 131; // 31 131 1313 13131 131313 etc..
    var hash uint64 = 0;
    for i := 0; i < len(str); i++ {
        hash = hash * seed + uint64(str[i])
    }
    return (hash & 0x7FFFFFFFFFFFFFFF)
}

// SDBM Hash
func SDBMHash(str []byte) uint32 {
    var hash uint32 = 0;
    for i := 0; i < len(str); i++ {
        // equivalent to: hash = 65599*hash + uint32(str[i]);
        hash = uint32(str[i]) + (hash << 6) + (hash << 16) - hash;
    }
    return (hash & 0x7FFFFFFF);
}

// SDBM Hash 64
func SDBMHash64(str []byte) uint64 {
    var hash uint64 = 0;
    for i := 0; i < len(str); i++ {
        // equivalent to: hash = 65599*hash + uint32(str[i]);
        hash = uint64(str[i]) + (hash << 6) + (hash << 16) - hash;
    }
    return (hash & 0x7FFFFFFFFFFFFFFF);
}

// RS Hash Function
func RSHash(str []byte) uint32 {
    var b uint32 = 378551;
    var a uint32 = 63689;
    var hash uint32 = 0;
    for i := 0; i < len(str); i++ {
        hash = hash * a + uint32(str[i]);
        a *= b;
    }
    return (hash & 0x7FFFFFFF);
}

// RS Hash Function 64
func RSHash64(str []byte) uint64 {
    var b    uint64 = 378551;
    var a    uint64 = 63689;
    var hash uint64 = 0;
    for i := 0; i < len(str); i++ {
        hash = hash * a + uint64(str[i]);
        a *= b;
    }
    return (hash & 0x7FFFFFFFFFFFFFFF);
}

// JS Hash Function
func JSHash(str []byte) uint32 {
    var hash uint32 = 1315423911;
    for i := 0; i < len(str); i++ {
        hash ^= ((hash << 5) + uint32(str[i]) + (hash >> 2));
    }
    return (hash & 0x7FFFFFFF);
}

// JS Hash Function 64
func JSHash64(str []byte) uint64 {
    var hash uint64 = 1315423911;
    for i := 0; i < len(str); i++ {
        hash ^= ((hash << 5) + uint64(str[i]) + (hash >> 2));
    }
    return (hash & 0x7FFFFFFFFFFFFFFF);
}

// P. J. Weinberger Hash Function
func PJWHash(str []byte) uint32 {
    var BitsInUnignedInt uint32 = (4 * 8);
    var ThreeQuarters    uint32 = ((BitsInUnignedInt  * 3) / 4);
    var OneEighth        uint32 = (BitsInUnignedInt / 8);
    var HighBits         uint32 = (0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
    var hash uint32             = 0;
    var test uint32             = 0;
    for i := 0; i < len(str); i++ {
        hash = (hash << OneEighth) + uint32(str[i]);
        if test = hash & HighBits; test != 0 {
            hash = ((hash ^ (test >> ThreeQuarters)) & (^HighBits + 1));
        }
    }
    return (hash & 0x7FFFFFFF);
}

// P. J. Weinberger Hash Function 64
func PJWHash64(str []byte) uint64 {
    var BitsInUnignedInt uint64 = (4 * 8);
    var ThreeQuarters    uint64 = ((BitsInUnignedInt  * 3) / 4);
    var OneEighth        uint64 = (BitsInUnignedInt / 8);
    var HighBits         uint64 = (0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
    var hash             uint64 = 0;
    var test             uint64 = 0;
    for i := 0; i < len(str); i++ {
        hash = (hash << OneEighth) + uint64(str[i]);
        if test = hash & HighBits; test != 0 {
            hash = ((hash ^ (test >> ThreeQuarters)) & (^HighBits + 1));
        }
    }
    return (hash & 0x7FFFFFFFFFFFFFFF);
}

// ELF Hash Function
func ELFHash(str []byte) uint32 {
    var hash uint32 = 0;
    var x    uint32 = 0;
    for i := 0; i < len(str); i++ {
        hash = (hash << 4) + uint32(str[i]);
        if x = hash & 0xF0000000; x != 0 {
            hash ^= (x >> 24);
            hash &= ^x + 1;
        }
    }
    return (hash & 0x7FFFFFFF);
}

// ELF Hash Function 64
func ELFHash64(str []byte) uint64 {
    var hash uint64 = 0;
    var x    uint64 = 0;
    for i := 0; i < len(str); i++ {
        hash = (hash << 4) + uint64(str[i]);
        if x = hash & 0xF0000000; x != 0 {
            hash ^= (x >> 24);
            hash &= ^x + 1;
        }
    }
    return (hash & 0x7FFFFFFFFFFFFFFF);
}

// DJB Hash Function
func DJBHash(str []byte) uint32 {
    var hash uint32 = 5381;
    for i := 0; i < len(str); i++ {
        hash += (hash << 5) + uint32(str[i]);
    }
    return (hash & 0x7FFFFFFF);
}

// DJB Hash Function 64
func DJBHash64(str []byte) uint64 {
    var hash uint64 = 5381;
    for i := 0; i < len(str); i++ {
        hash += (hash << 5) + uint64(str[i]);
    }
    return (hash & 0x7FFFFFFFFFFFFFFF);
}

// AP Hash Function
func APHash(str []byte) uint32 {
    var hash uint32 = 0;
    for i := 0; i < len(str); i++ {
        if ((i & 1) == 0) {
            hash ^= ((hash << 7) ^ uint32(str[i]) ^ (hash >> 3));
        } else {
            hash ^= (^((hash << 11) ^ uint32(str[i]) ^ (hash >> 5)) + 1);
        }
    }
    return (hash & 0x7FFFFFFF);
}

// AP Hash Function 64
func APHash64(str []byte) uint64 {
    var hash uint64 = 0;
    for i := 0; i < len(str); i++ {
        if ((i & 1) == 0) {
            hash ^= ((hash << 7) ^ uint64(str[i]) ^ (hash >> 3));
        } else {
            hash ^= (^((hash << 11) ^ uint64(str[i]) ^ (hash >> 5)) + 1);
        }
    }
    return (hash & 0x7FFFFFFFFFFFFFFF);
}

 

Go语言/位操作/取反/异或/左移/右移

package main

import (
    "fmt"
)

// 获取0-n之间的所有偶数
func even(a int) (array []int) {
    for i := 0; i < a; i++ {
        if i&1 == 0 { // 位操作符&与C语言中使用方式一样
            array = append(array, i)
        }
    }
    return array
}

// 互换两个变量的值
// 不需要使用第三个变量做中间变量
func swap(a, b int) (int, int) {
    a ^= b // 异或等于运算
    b ^= a
    a ^= b
    return a, b
}

// 左移、右移运算
func shifting(a int) int {
    a = a << 1
    a = a >> 1
    return a
}

// 变换符号
func nagation(a int) int {
        // 注意: C语言中是 ~a+1这种方式
    return ^a + 1 // Go语言取反方式和C语言不同,Go语言不支持~符号。
}

func main() {
    fmt.Printf("even: %v\n", even(100))
    a, b := swap(100, 200)
    fmt.Printf("swap: %d\t%d\n", a, b)
    fmt.Printf("shifting: %d\n", shifting(100))
    fmt.Printf("nagation: %d\n", nagation(100))
}

 

常用HASH算法 代码 & 比较

  • 常用的字符串Hash函数还有ELFHash,APHash等等,都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数,这些函数几乎不可能找到碰撞。
  • 常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。对于以上几种哈希函数,我对其进行了一个小小的评测。
Hash函数  数据1 数据2   数据3    数据4     数据1得分 数据2得分    数据3得分    数据4得分     平均分
BKDRHash    2   0     4774    481       96.55   100         90.95       82.05       92.64
APHash      2   3     4754    493       96.55   88.46       100         51.28       86.28
DJBHash     2   2     4975    474       96.55   92.31       0           100         83.43
JSHash      1   4     4761    506       100     84.62       96.83       17.95       81.94
RSHash      1   0     4861    505       100     100         51.58       20.51       75.96
SDBMHash    3   2     4849    504       93.1    92.31       57.01       23.08       72.41
PJWHash     30  26    4878    513       0       0           43.89       0           21.95
ELFHash     30  26    4878    513       0       0           43.89       0           21.95

Continue reading "常用HASH算法 代码 & 比较"

B树和B+树的总结

B树/B-树

为什么要B树

磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片旋转到指定位置以后,移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程,而定位是磁盘的存取中花费时间比较大的一块,毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候,显然定位是一个非常花费时间的过程,但是我们可以通过B树进行优化,提高磁盘读取时定位的效率。

为什么B类树可以进行优化呢?我们可以根据B类树的特点,构造一个多阶的B类树,然后在尽量多的在结点上存储相关的信息,保证层数尽量的少,以便后面我们可以更快的找到信息,磁盘的I/O操作也少一些,而且B类树是平衡树,每个结点到叶子结点的高度都是相同,这也保证了每个查询是稳定的。 Continue reading "B树和B+树的总结"